perm filename ALLHEU.TEX[AM,DBL]1 blob
sn#394265 filedate 1978-11-10 generic text, type T, neo UTF8
00100 .ASEC(AM's Heuristics)
00200
00300 .QQ
00400
00500 Infallible rules of discovery leading to the solution of all possible
00600 mathematical problems would be more desirable than the philosophers'
00700 stone, vainly sought by the alchemists. Such rules would work magic;
00800 but there is no such thing as magic. To find unfailing rules
00900 applicable to all sorts of problems is an old philosophical dream;
01000 but this dream will never be more than a dream.
01100
01200 -- Polya
01300
01400 .ESS
01500
01600 .QQ
01700
01800 To the extent that a professor of music at a conservatoire can assist
01900 his students in becoming familiar with the patterns of harmony and
02000 rhythm, and with how they combine, it must be possible to assist
02100 students in becoming sensitive to patterns of reasoning and how they
02200 combine. The analogy is not far-fetched at all
02300
02400 -- Dijkstra
02500
02600 .ESS
02700
02800
02900 This appendix lists all the heuristics with which AM is initially
03000 provided. They are organized by concept, most general concepts
03100 first. Within a concept, they are organized into four groups:
03200
03300 .BN
03400
03500 ⊗8#\0 Fillin: rules for filling in new entries on various facets.
03600
03700 ⊗8#\0 Check: rules for patching up existing entries on various
03800 facets.
03900
04000 ⊗8#\0 Suggest: rules which propose new tasks to break AM out of
04100 stagnant loops.
04200
04300 ⊗8#\0 Interest: criteria for estimating the interestingness of
04400 various entities.
04500
04600 .E
04700
04800 Each heuristic is presented in English translation. Whenever there is
04900 a very tricky, non-obvious, or brilliant translation of some English
05000 clause into LISP, a brief note will follow about how that is coded.
05100 Also given (usually) are some example(s) of its use, and its overall
05200 importance. Concepts which have no heuristics are not present in
05300 this appendix.
05400
05500 .ONCE TURN ON ``{}``
05600
05700 Hundreds of heuristics were planned on paper but never coded (e.g.,
05800 those dealing with proof techniques, those dealing with the drives
05900 and rewards of generalized message senders/receivers), and whole
06000 classes of rules were coded but never used by AM during any of its
06100 runs (e.g., how to deal with contradictions, how to deal with Intu's
06200 facets). Such superfluous rules will not be included here. They
06300 would raise the total number of heuristic rules from {[3]TRULES} to
06400 about 500.
06500
06600 .ONCE TURN ON ``{}``
06700
06800 The rule numbering in this Appendix is referred to occasionally in
06900 other appendices. The total number of rules coded in AM is actually
07000 higher, since many rules are present but never used, and since many
07100 rules listed with one number here are really ⊗4several\0 rules in
07200 LISP (e.g., see rules {[3]QUADRULE} and {[3]DOUBRULE}).
07300
07400 .if false then start;
07500
07600 It would be advantageous to have a cross-indexing of the body of heuristics
07700 along several dimensions (a multiple sorting by a small set of key parameters):
07800 sorted by interest, by relevance (the current arrangement),
07900 by cost, by payoff, by frequency of usage, etc.
08000 This is left as a starred excercise for the interested reader.
08100 .end;
08200
08300 .ALLHEU: ASECNUM ;
08400
08500 .ALLEHU: ASECNUM ;
08600
08700 .SKIP TO COLUMN 1;
08800
00100 .ASSEC(Heuristics for dealing with Anything)
00200
00300 All these rules deal with any item X, be it concept, atom, event, etc.
00400 These rules are about as general -- and as ⊗4weak\0 -- as one can imagine.
00500
00600 .HH(Anything,Suggest)
00700
00800 .BH
00900
01000 λλ If AM has recently referenced entity X,
01100
01200 Then boost the priority of any tasks involving X.
01300
01400 .ES
01500
01600 .FOA1: BNN;
01700
01800 .BH
01900
02000 λλ If the user has recently referred to X,
02100
02200 Then boost the priority of any tasks involving X.
02300
02400 .E
02500
02600
02700 The above two rules simply reaffirm the idea of ``focus of attention".
02800 The boost in ratings is only slight, and only temporary (it decays toward zero
02900 exponentially
03000 with time). Besides this gradual decline in task ratings,
03100 the rule below explicitly
03200 modulates this boosting, so that infinite loops can be avoided.
03300
03400 .BH
03500
03600 λλ If AM has recently dealt with X with poor results,
03700
03800 Then lower the priority rating of all tasks involving X.
03900
04000 .ES
04100
04200 .BH
04300
04400 λλ If AM just referenced X and almost succeeded, but not quite,
04500
04600 Then look for a very similar entity Y, and retry the activity with Y in place of X.
04700
04800 .E
04900
05000 There is a separate precise meaning for ``almost succeed", ``similar entity", and
05100 ``retry" for each kind of entity and activity that might be involved. For example,
05200 if the activity were a ⊗4task\0 (say to fill in examples of Odd-primes)
05300 and the entity
05400 X were a ⊗4concept\0 (in this case, Odd-primes),
05500 then a `similar entity' might be the concept Odd-numbers, and in that case
05600 the result of this rule would be
05700 ⊗4a new task\0 (to fill in examples of Odd-numbers).
05800 If the failure occurred while AM was trying to access the examples facet of Primes,
05900 with X=Examples, then a `similar entity' might be the Boundary-examples facet, and
06000 the above rule would suggest that AM access instead the Boundary-examples facet of Primes.
06100 Of course, this rule is so weak that it is not often of much help.
06200
06300
06400 .BH
06500
06600 λλ If
06700 space is running out, and
06800 AM has not referenced X for a long time, and X is taking up a lot of space,
06900 and no important conjectures reference X,
07000
07100 Then X may be forgotten and its space liberated.
07200 Probably the user should be informed of this, at least tersely.
07300
07400 .E;
07500
07600 .FOA2: BNN;
07700
07800 Just a general-purpose directive for emergency garbage-collection.
07900
08000 .HH(Anything,Interest)
08100
08200 .A4ANYTHING: SSECNUM;
08300
08400 .A4ANYTHINGI: PAGE;
08500
08600 .BH
08700
08800 λλ Any entity X
08900 is interesting if it is referred to in several interesting conjectures.
09000
09100 .ES
09200
09300 .BH
09400
09500 λλ Any entity X
09600 is interesting if it is related (via a rare, interesting relation) to another
09700 entity which arose in a very different way and is not obviously tied to X.
09800
09900 .E
10000
10100 Unexpected connections are worth closer examination, typically.
10200 X might be `related to' Y because F(X)=Y (for some very interesting
10300 operation F), because Y(X) is true (for some rarely-satisfied predicate Y),
10400 because some conjecture involving X is syntactically identical to the same conjecture
10500 involving Y, etc.
10600
10700 .BH
10800
10900 λλ Entity X is (tentatively) interesting if there is an analogy in which
11000 X corresponds to Y, and Y has turned out to be very interesting.
11100
11200 .ES
11300
11400 .BH
11500
11600 λλ If entity X is an example of concept C, and X satisfies some
11700 features on C.Int,
11800
11900 Then X is interesting, and C's Interestingness features
12000 will indicate a numeric rating for X.
12100
12200 .E
12300
12400 .SYNR1: BNN;
12500
12600 This is practically the definiton of the Int facet. Below is a much more ususual rule:
12700
12800 .BH
12900
13000 λλ If entity X is an example of concept C, and X satisfies absolutely none of the
13100 features on C.Int, and X is just about the only C which doesn't satisfy something,
13200
13300 Then X is interesting because of its unusual boringness.
13400
13500 .E
13600
13700 Since most singletons are interesting because all pairs of their elements
13800 are Equal, the above rule says it would be interesting actually to find a singleton
13900 for which ⊗4not\0 all pairs of its members were equal. While it would be interesting, AM has
14000 very little chance of finding such a critter.
14100
00100 .ASSECP(Heuristics for dealing with Any-concept)
00200
00300 This concept has a huge number of heuristics. For that reason, I have partitioned
00400 off -- both here and in AM itself$$
00500 Thus the LISP program has a separate concept called ``Examples-of-any-concept",
00600 another concept called ``Definitions-of-any-concept", etc.
00700 $ -- the heuristics which apply to each kind of facet.
00800
00900 .A4ANYBINGF: PAGE;
01000
01100 .ASSSEC(Heuristics for any facet of Any-concept)
01200
01300 The first set of heuristics we'll look at are very general, applying to no
01400 particular facet exactly.
01500
01600 .HH(Any-concept,Fillin)
01700
01800 .BH
01900
02000 λλ When trying to fill in facet F of concept C, for any C and F,
02100
02200 If C is analogous to concept X, and X.F has some entries,
02300
02400 Then try to construct the analogs of those entries, and see if they
02500 are really valid entries for C.F.
02600
02700 .E
02800
02900 Recall that ``C.F" is shorthand for ``facet F of concept C". This rule simply
03000 says that if an analogy exists between two concepts C and X,
03100 then it may be strong enough to map entries on X.F into entries for C.F.
03200 Note that F can be any given facet.
03300 There is an analogy between Sets and Bags, and AM uses the above rule to turn
03400 the extreme example of Sets -- the empty set -- into the extreme kind of bag.
03500
03600
03700
03800 .HH(Any-concept,Suggest)
03900
04000 .BH
04100
04200 λλ If the F facet of concept X is blank,
04300
04400 Then consider trying to fill it in.
04500
04600 .E
04700
04800 .NEWCEX: BNN;
04900
05000
05100 The above super-weak rule will result in a new task being added to the agenda,
05200 for every blank facet of every concept. It is more of a legal move generator
05300 than a plausible move proposer.
05400 The rating of each such task will depend on the Worth of the concept X and the
05500 overall worth of the type F facet, but in all cases will be ⊗4very small.\0
05600 The ``emptiness" of a facet is always a valid
05700 reason for trying to fill it in,
05800 but never an a priori important reason.
05900 So the net effect of the rule is to slightly bias AM toward working on blank
06000 -- rather than non-blank -- facets.
06100
06200 .BH
06300
06400 λλ While trying to fill in facet F of concept C, for any C and F,
06500 if C is known to be similar to some other concept D, except for difference d,
06600
06700 Then try to fill in C.F by selecting items from D.F for which d is nonexistent.
06800
06900 .E
07000
07100 .LOOKDIF: BNN;
07200
07300 This rule is made more specific when F is actually known, and hence
07400 the format of
07500 d is actually determined. For example, if C=Reverse-at-all-levels, F=examples,
07600 then (at one particular moment) a note is found on the Conjecs facet of
07700 concept C which says that C is just like the concept D=Reverse-top-level,
07800 except C also recurs on the nonatomic elements of its arguments, whereas D doesn't.
07900 Thus d is made null by choosing examples of D for which there are no nonatomic
08000 elements. So an example like ⊗3`Reverse-top-level(<a b c>)=<c b a>'\0 will be
08100 selected and will lead to the proposed example
08200 ⊗3`Reverse-at-all-levels(<a b c>)=<c b a>'\0, which is in fact valid.
08300
08400 .BH
08500
08600 λλ After dealing with concept C,
08700
08800 Slightly, temporarily boost
08900 the priority value
09000 of each existing task which involves an Active concept
09100 whose domain or range is C.
09200
09300 .E
09400
09500 .FROB1: BNN;
09600
09700 This is done efficiently using the In-dom-of and In-ran-of facets of C.
09800 A typical usage was after checking the just-filled-in
09900 examples of Bags, when AM slightly
10000 boosted the rating of filling in examples of Bag-union, and this task
10100 just barely squeaked through as the next one to be chosen.
10200 Note that the rule reinforced that task twice, since both domain and range
10300 of Bag-union are bags.
10400
10500
10600
10700 .HH(Any-concept,Check)
10800
10900
11000 .BH
11100
11200 λλ When checking facet F of concept C, (for any F and C,)
11300
11400 Prune away at the entries there until the facet's size is reduced to
11500 the size which C merits.
11600
11700 .E
11800
11900 .SEZ1: BNN;
12000
12100 The algorithm for doing this is as follows: The Worth of C is multiplied by
12200 the overall worth of facet type F. This is normalized in two ways, yielding
12300 the maximum amount of list cells that C.F may occupy, and also yielding the
12400 maximum number of separate entries to keep around on C.F. If either limit
12500 is being exceeded, then an entry is plucked at random (but weighted to favor
12600 selection from the rear of the facet) and excised. This repeats as long as
12700 C.F is oversized. As space grows tight, the normalization weights decline,
12800 so each concept's allocation is reduced.
12900
13000 .BH
13100
13200 λλ When checking facet F of concept C,
13300
13400 Eliminate redundant entries.
13500
13600 .E
13700
13800 .SEZ2: BNN;
13900
14000 Although it might conceivably mean something for an entry to occur twice,
14100 this was never desirable for the set of facets which each AM concept possessed.
14200
14300
14400 .HH(Any-concept,Interest)
14500
14600 The interest features apply to tell how interesting a concept is, and are
14700 rarely subdivided by relevant facet. That is, most of the reasons that
14800 Any concept might be interesting will be given below.
14900
15000 .BH
15100
15200 λλ A concept X is interesting if X.Conjecs contains some interesting entries.
15300
15400 .ES
15500
15600 .A4ANYB: SSECNUM;
15700
15800 .A4ANYBINGI: PAGE;
15900
16000
16100 .BH
16200
16300 λλ A concept is interesting if its boundary accidentally coincides with
16400 another, well-known, interesting concept.
16500
16600 .E
16700
16800 The boundary of a concept means the items which just barely fall into
16900 (or just barely miss satisfying) the definition of that concept. Thus the
17000 boundary of Primes might include 1,2,3,4.
17100 If the boundary of Even numbers includes numbers differing by at most 1 from
17200 an even number, then clearly their boundary is ⊗4all\0 numbers. Thus it coincides
17300 with the already-known concept Numbers, and this makes Even-nos more interesting.
17400 This expresses the property we intuitively understand as: no number is very far
17500 from an even number.
17600
17700 .BH
17800
17900 λλ A concept is interesting if its boundary accidentally coincides with
18000 the boundary of another, very different, interesting concept.
18100
18200 .E
18300
18400 Thus, for example, Primes and Numbers are both a little more interesting
18500 since the extreme cases of numbers are all boundary cases of primes.
18600 Even numbers and Odd numbers both have the same boundary, namely Numbers.
18700 This is a tie between them, and slightly raises AM's interest in both concepts.
18800
18900 .BH
19000
19100 λλ A concept is interesting if it is -- accidentally -- precisely the
19200 boundary of some other, interesting concept.
19300
19400 .E
19500
19600 In the case mentioned for the above rule, Numbers is raised in interest
19700 because it turns out to be the boundary for even and odd numbers.
19800
19900
20000 .BH
20100
20200 λλ A concept is boring if, after several attempts, only a couple
20300 examples are found.
20400
20500 .E
20600
20700 .MAH1: BNN;
20800
20900 Another rule indicates, in such situations, that the concept may be
21000 forgotten and replaced by some conjecture.
21100
21200 .BH
21300
21400 λλ Concept C is interesting if some normally-inefficient operation F
21500 can be efficiently performed on C's.
21600
21700 .E
21800
21900 Thus it is very fast to perform Insert of items into lists because
22000 (i) no pre-existence checking need be done (as with sets and osets),
22100 and (ii) no ordered merging need be done (as with bags).
22200 So ``Lists" is an interesting concept for that reason, according to the
22300 above rule.
22400
22500 .BH
22600
22700 λλ Concept C is interesting if each example of C accidentally seems to
22800 satisfy the otherwise-rarely satisfied predicate P, or (equivalently)
22900 if there is an unusual conjecture involving C.
23000
23100 .E
23200
23300
23400 This is almost a primitive affirmation of intererestingness.
23500
23600
23700 .BH
23800
23900 λλ Concept C is interesting if C is closely related to the very interesting
24000 concept X.
24100
24200 .E
24300
24400
24500 This is intererestingness by association. AM was interested in
24600 Divisors-of because it was closely related to TIMES, which had
24700 proven to be a very interesting concept.
24800
24900 .BH
25000
25100 λλ Concept C is interesting if there is an analogy in which
25200 C corresponds to Y, and the analogs of the Interest features of Y
25300 indicate that C is interesting.
25400
25500 .E
25600
25700 This might have been a very useful rule, if only there had been more
25800 decent analogies floating around the system. As it was, the rule was
25900 rarely used to advantage. It essentially says that the analogs of
26000 Interest criteria are themselves (probably) valid criteria.
26100
26200 .BH
26300
26400 λλ A concept C is interesting if one of its generalizations or specializations
26500 turns out to be unexpectedly very interesting.
26600
26700 .E
26800
26900 .AINT1: BNN;
27000
27100 ``Unexpected" means that the interesting property hadn't already been observed for
27200 C. If C is interesting in some way, and then one of its generalizations is
27300 seen to be interesting
27400 in exactly
27500 the same way, then that is ``expected".
27600 It's almost more interesting if the second concept unexpectedly ⊗4lacks\0
27700 some fundamental property about C. At least in that case AM might learn something
27800 about what gives C that property. In fact, AM has this rule:
27900
28000 .BH
28100
28200 λλ If concept C possesses some very interesting property lacked by one of its
28300 specializations S,
28400
28500 Then both C and S become slightly more interesting.
28600
28700 .E; ONCE TURN ON ``{}``
28800
28900 In the LISP program, ths is closely linked with rule {[3]INTERMES}.
29000
29100 .BH
29200
29300 λλ If a concept C is re-derived in a new way, that makes it more interesting.
29400
29500 If concepts C1 and C2 turn out to be equivalent concepts, then merge them.
29600 The combined concept is now more interesting than either of its predecessors.
29700
29800 .E
29900
30000 .REDERIVE: BNN; ONCE TURN ON ``{}``;
30100
30200 The two conditionals above are really the same rule, so they aren't given
30300 separate numbers. C1 and C2 might be conjectured equivalent because their
30400 examples coincide, each is a generalization of the other, their definitions
30500 can be formally shown to be equivalent, etc.
30600 This rule is similar in spirit to rule number {[3]GSCHAIN}.
30700
30800
00100 . ASSSEC(Heuristics for the Examples facets of Any-concept)
00200
00300 .ABXHP: PAGE;
00400
00500 The following heuristics are used for dealing with the many kinds of
00600 examples facets which a concept can possess: non-examples, boundary
00700 examples, Isa links, etc.
00800
00900 .HH(Any-concept . Examples,Fillin)
01000
01100 .BH
01200
01300 λλ To fill in examples of X, where X is a kind of Y (for some more
01400 general concept Y),
01500
01600 Inspect the examples of Y; some of them may be examples of X as well.
01700
01800 The further removed Y is from X, the less cost-effective this rule
01900 is.
02000
02100 .E
02200
02300 .LOOKGEX: BNN;
02400
02500 For the task of filling in Empty-structures, AM knows that concept is
02600 a specialization of Structures, so it looks over all the then-known
02700 examples of Structures. Sure enough, a few of them are empty (satisfy
02800 Empty-structures.Defn). Similarly, for the task of filling in
02900 examples of Primes, this rule would have AM notice that Primes is a
03000 kind of Number, and therefore look over all the known examples of
03100 Number. It would not be cost-effective to look for primes by testing
03200 each example of Anything, and the third and final clause in the above
03300 rule recognizes that fact.
03400
03500 .BH
03600
03700 λλ To fill in non-examples of concept X,
03800
03900 Search the specializations of X. Look at all their non-examples.
04000 Some of them may turn out to be non-examples of X as well.
04100
04200 .E
04300
04400 This rule is the counterpart of the last one, but for
04500 ⊗4non\0-examples. As expected, this was less useful than the
04600 preceding positive rule.
04700
04800 .BH
04900
05000 λλ If the current task is to fill in examples of any concept X,
05100
05200 Then one way to get them is to symbolically instantiate a definition
05300 of X.
05400
05500 .E
05600
05700 .INDEF: BNN;
05800
05900 That rule simply says to use some known tricks, some hacks, to wring
06000 examples from a declarative definition. One trick AM knows about is
06100 to plug already-known examples of X into the recursive step of a
06200 definition. Another trick is simply to try to instantiate the base
06300 step of a recursive definition. Another trick is to take a
06400 definition of the form ``λ (x) x isa P, and <⊗4sub-expression\0>``,
06500 work on instantiating just the ⊗4sub-expression\0, and then pop back
06600 up and see which of those items are P's.
06700
06800 .BH
06900
07000 λλ If the current task is to fill in non-examples of concept X,
07100
07200 Then one fast way to get them is to pick any random item, any example
07300 of Anything, and check that it fails X.Defn.
07400
07500 .E
07600
07700 This is an affirmation that for any concept X, most things in the
07800 universe will probably not be X's. This rule was almost never used to
07900 good advantage: non-examples of a concept X were never sought unless
08000 there was some reason to expect that they might not exist. In those
08100 cases, the presumption of the above rule was wrong, and it failed.
08200 That is, the rule succeeded iff it was not needed.$$ Catch-22? $
08300
08400 .BH
08500
08600
08700 λλ To fill in examples of concept X,
08800
08900 If X.View tells how to view a Z as if it were an X, and some examples
09000 of Z are known,
09100
09200 Then just run X.View on those examples, and check that the results
09300 really are X's.
09400
09500 .E
09600
09700 Thus examples of osets were found by viewing other known examples of
09800 structures (e.g., examples of sets) as if they were osets.
09900
10000 .BH
10100
10200 λλ To fill in examples of concept X,
10300
10400 Find an operation whose range is X,$$ or at least INTERSECTS X. Use
10500 the In-ran-of facets and the rippling mechanism to find such an
10600 operation. $ and find examples of that operation being applied.
10700
10800 .E
10900
11000 To fill in examples of Even-nos, this rule might have AM notice the
11100 operation `Double'. Any example of Double will contain an example of
11200 an even number as its value: e.g., <3→6> contains the even number 6.
11300
11400 .BH
11500
11600 λλ If the current task is to fill in examples of concept X,
11700
11800 One bizarre way is to specialize X, adding a strong constraint to
11900 X.Defn, and then look for examples of that new specialization.
12000
12100 .E
12200
12300 Like the classical ``insane heuristic"$$ A harder task might be easier
12400 to do. A stronger theorem might be easier to prove. This is called ``The Inventor's
12500 Paradox", on page 121 of [Polya 57]. $,
12600 this sounds crazy but works embarassingly often. If I ask
12700 you to find numbers having a prime number of divisors, the rate at
12800 which you find them will probably be lower than if I'd asked you to
12900 find numbers with precisely 2 divisors. The ⊗4variety\0 of examples
13000 will suffer, of course. The converse of this heuristic -- for
13100 non-examples -- was deemed too unaesthetic to feed to AM.
13200
13300 .BH
13400
13500 λλ To fill in examples of X,
13600
13700 One inefficient method is to examine random examples of Anything,
13800 checking each by running X.Defn to see if it is an X. Slightly
13900 better is to ripple outward from X in all directions, testing all the
14000 examples of the concepts encountered.
14100
14200 .E
14300
14400 This is blind generate-and-test, and was (luckily) not needed much by
14500 AM.
14600
14700 .BH
14800
14900 λλ To find more examples of X (or: to find an extreme example of X),
15000 when a nice big example is known, and X has a recursive definition,
15100
15200 Try to plug the known example into the definition and produce a
15300 simpler one. Repeat this until an example is produced which satisfies
15400 the base-step predicate of the definition. That entity is then an
15500 extreme (boundary) example of X.
15600
15700 .E
15800
15900 For example, AM had a definition of a set as
16000
16100 .ONCE INDENT 0
16200
16300 ``Set(S) if S={} or if Set(Remove-random-element(S))." When AM found
16400 the big example {A,B,{{C},D},{{{E}}},F} by some other means, it used
16500 the above rule and on he recursive definition to turn this into
16600 {A,B,{{{E}}},F} by removing the randomly-chosen third element.
16700 {A,B,F} was produced next, followed by {B,F} and {F}. After that, {}
16800 was produced and the rule relinquished control.
16900
17000 .BH
17100
17200 λλ To find examples of X, when X has a recursive definition,
17300
17400 One method with low success rate but high payoff is to try to invert
17500 that definition, thereby creating a procedure for generating new
17600 examples.
17700
17800 .E
17900
18000 .INVDEF: BNN;
18100
18200 Using the previous example, AM was able to turn the recursive
18300 definition of a set into the program ``Insert-any-random-item(S)``,
18400 which turns any set into a (usually different and larger) new set.
18500 Since the rules which AM uses to do these transformations are very
18600 special-purpose, they are not worth detailing here. This is one very
18700 managable open problem, where someone might spend some months and
18800 create a decent body of definition-inversion rules. A typical rule
18900 AM has says:
19000
19100 .ONCE INDENT 0; PREFACE 0;
19200
19300 ``Any phrase matching `⊗4Removing an x and ensuring that P(x)\0' can be
19400 inverted and turned into this one: `⊗4Finding any random x for which
19500 P(x) holds, then inserting x'\0." The class of definitions which can
19600 be inverted using AM's existing rules is quite small; whenever AM
19700 needed to be able to invert another particular definition, the author
19800 simply supplied whatever rules would be required.
19900
20000 .BH
20100
20200 λλ While filling in examples of C,
20300
20400 if two constructs x and y are found which are very similar yet only
20500 one of which is an example of the concept C,
20600
20700 Then one is a boundary example of C, and the other is a boundary
20800 non-example,
20900
21000 and it's worth creating more boundary examples and boundary
21100 non-examples by slowly transforming x and y into each other.
21200
21300 .E
21400
21500 Thus when AM notices that {a} and {a,b,a} are similar yet not both
21600 sets, it creates {a,b}, {b,a}, {a,a} and sees which are and are not
21700 examples of sets. In this way, some boundary items (both examples and
21800 non-examples) are created. The rules for this slow transformation are
21900 again special purpose. They examine the difference between the items
22000 x and y, and suggest operators (e.g., Deletion) which will reduce
22100 that difference. This GPS-like strategy has been well studied by
22200 others, and its inferior implementation inside AM will not be
22300 detailed.
22400
22500 .BH
22600
22700 λλ If the main task now is to fill in examples of concept C,
22800
22900 Consider all the examples of ``first cousins" of C. Some of them might
23000 be examples of C as well.
23100
23200 .E
23300
23400 By ``first cousins", we mean all direct specializations of all direct
23500 generalizations of a concept, or vice versa. That is, going up once
23600 along a Genl link, and then down once along a Spec link (or going
23700 down one link and then up one link).
23800
23900 .BH
24000
24100 λλ If the main task now is to fill in boundary (non-)examples of
24200 concept C,
24300
24400 Consider all the boundary (non-)examples of ``first cousins" of C.
24500 Some of them might lie on the boundary of C as well.
24600
24700 .E
24800
24900 If they turn out not to be boundary examples, they can be recorded as
25000 boundary non-examples, and vice versa.
25100
25200 .BH
25300
25400 λλ To fill in Isa links of concept X, (that is, to find a list of
25500 concepts of which X is an example),
25600
25700 Just ripple down the tree of concepts, applying a definition of each
25800 concept. Whenever a definition fails, don't waste time trying any of
25900 its specializations. The Isa's of X are then all the concepts tried
26000 whose definitions passed X.
26100
26200 .E
26300
26400 When a new concept is created, e.g., a new composition, this rule can
26500 ascertain the most specific Isa links that can be attached to it.
26600 Another use for this rule would be: If the Isa link network ever got
26700 fouled up (contained paradoxes), this rule could be used to
26800 straighten everything out (with a logarithmic expenditure of time).
26900
27000
27100
27200 .HH(Any-concept . Examples,Suggest)
27300
27400 .BH
27500
27600 λλ If some (but not most) examples of X are also examples of Y (for
27700 some concept Y),
27800
27900 and some (but not most) examples of Y are also examples of X,
28000
28100 Create a new concept defined as the intersection of those two
28200 concepts (X and Y). This will be a specialization of both concepts.
28300
28400 .E
28500
28600 .MAH2: BNN;
28700
28800 If you hapen to notice that some primes are palindromic, this rule
28900 would suggest creating a brand new concept, defined as the set of
29000 numbers which are both palindromic and prime. AM never actually
29100 noticed this, since it represented all numbers in unary. If pushed,
29200 AM will define Palindrome(n) to mean that the sequence of exponents
29300 of prime factors is symmetric; thus
29400 2⊗A3\03⊗A8\05⊗A1\07⊗A1\011⊗A8\013⊗A3\0 is palindromic in AM's sense
29500 because the sequence of its exponents (3 8 1 1 8 3) is unchanged upon
29600 reversal. In this sense, the only Prime palindromes are the primes
29700 themselves (or: just `2', depending upon the precise definition).
29800
29900 .BH
30000
30100 λλ If very few examples of X are found,
30200
30300
30400 Then add the following task to the agenda: ``Generalize the concept
30500 X", for the following reason: ``X's are quite rare; a slightly less
30600 restrictive concept might be more interesting".
30700
30800 .E
30900
31000 Of course, AM contains a precise meaning for the phrase ``very few".
31100 When AM looks for primes among examples of already-known kinds of
31200 numbers, it will find dozens of non-examples for every example of a
31300 prime it uncovers. ``Very few" is thus naturally implemented as a
31400 statistical confidence level. AM uses this rule when very few
31500 examples of Equality are found readily.
31600
31700 .BH
31800
31900 λλ If very many examples of X are found in a short period of time,
32000
32100 Then try to create a new, specialized version of X.
32200
32300 .E
32400
32500 .SPEASY: BNN;
32600
32700 This is similar to the preceding rule. Since numbers are easy to
32800 find, this might cause us to look for certain more interesting
32900 subclasses of numbers to study.
33000
33100 .BH
33200
33300 λλ If there are no known examples for the interesting concept X,
33400
33500 Then consider spending some time looking for such examples.
33600
33700 .E
33800
33900 I've heard of a math student who defined a set of number which had
34000 quite marvelous properties. After the 20↑t↑h incredible theorem about
34100 them he'd proved, someone noticed that the set was empty. The danger
34200 of unwittingly dealing with a vacuous concept is even worse for a
34300 machine than for a human mathematician. The above rule explicitly
34400 prevents that.
34500
34600 .BH
34700
34800 λλ If the totality of examples of concept C is too small to be
34900 interesting,
35000
35100 Then consider these reactions: (i) generalize C; (ii) forget C
35200 completely; (iii) replace C by one conjecture.
35300
35400 .E
35500
35600 This is a good example of when a task like ⊗6"Fill in generalizations
35700 of Numbers-with-α1-divisors"\0 might get proposed with a
35800 high-priority reason. The class of entities which C encompasses is
35900 simply too small, too trivial to be worth maintaining a separate
36000 concept. When C is numbers-with-α1-divisor, C is really just another
36100 disguise for the singleton set {1}. The above rule might cause a new
36200 task to be added to the agenda, ⊗6Fill in generalizations of
36300 Numbers-with-α1-divisor\0. When that task is executed, AM might
36400 create the concept Numbers-with-odd-no-of-divisors,
36500 Numbers-with-prime-number-of-divisors, etc. Besides generalizing
36600 that concept, the above rule gives AM two other alternatives. AM may
36700 simply obliterate the nearly-vacuous concept, perhaps leaving around
36800 just the statement ``⊗41 is the only number with one divisor\0". That
36900 conjecture might be tacked onto the Conjecs facet of Divisors-of. The
37000 actual rule will specify criteria for deciding which of the three
37100 alternatives to try. In fact, AM really starts all three activities:
37200 a task will always be created and added to the agenda (to generalize
37300 C), the vacuous concept will be tagged as ``forgettable", and AM will
37400 attempt to formulate a conjecture (the only items satisfying C.Defn
37500 are C.Exs).
37600
37700 .BH
37800
37900 λλ If the totality of examples of concept C is too large to be
38000 interesting,
38100
38200 Then consider these three possible reactions: (i) specialize C; (ii)
38300 forget C completely; (iii) replace C by one conjecture.
38400
38500 .E
38600
38700 This is analogous to the preceding rule, but is used far less
38800 frequently. One common use is when a disjunction of two concepts has
38900 been formed which is accidentally large or already-known (e.g.,
39000 ``Evens ∪ Odds" would be replaced by a conjecture).
39100
39200 .BH
39300
39400 λλ After filling in examples of C, if some examples were found,
39500
39600 Look at all the operations which can be applied to C's (that is,
39700 access C.In-dom-of), find those which are interesting but which have
39800 no known examples, and suggest that AM fill in examples for them,
39900 because some items are now known which are in their domain, namely
40000 C.Exs.
40100
40200 .E
40300
40400 This rule had AM fill in examples of Set-insertion, as soon as some
40500 examples of Sets had been found.
40600
40700 .BH
40800
40900 λλ After filling in examples of C, if some examples were found,
41000
41100 Consider the task of Checking the examples facet of concept C.
41200
41300 .E
41400
41500 This was very frequently used during AM's runs.
41600
41700 .BH
41800
41900 λλ After checking examples of C, if many examples remain,
42000
42100 Consider the task of `Filling in some Conjecs for C'.
42200
42300 .E
42400
42500 This was used often by AM. After checking the examples of C, AM would
42600 try to empirically formulate some interesting conjecture about C.
42700
42800 .BH
42900
43000 λλ After successfully filling in non-examples of X, if no examples
43100 exist,
43200
43300 If AM has not recently tried to find examples of X, then it should do
43400 so.
43500
43600 If AM has recently tried and failed to find examples, consider the
43700 conjecture that X is vacuous, empty, null, always-False. Consider
43800 generalizing X.
43900
44000 .ES
44100
44200 .BH
44300
44400 λλ After trying in vain to find some non-examples of X, if many
44500 examples exist,
44600
44700 Consider the conjecture that X is universal, always-True. Consider
44800 specializing X.
44900
45000 .ES
45100
45200 .BH
45300
45400 λλ After successfully filling in examples of X, if no non-examples
45500 exist,
45600
45700 If AM has not recently tried to find non-examples of X, then it
45800 should consider doing so.
45900
46000 If AM has recently tried and failed to find non-examples, consider
46100 the conjecture that X is universal, always-True. Consider
46200 specializing X.
46300
46400 .ES
46500
46600 .BH
46700
46800 λλ After trying in vain to find some examples of X,
46900
47000 If many non-examples exist,
47100
47200 Consider the conjecture
47300 that X is vacuous, null, empty, always-False. Consider generalizing X.
47400
47500 .ES
47600
47700
47800
47900 .HH(Any-concept . Examples,Check)
48000
48100 .BH
48200
48300 λλ If the current task is to Check Examples of concept X,
48400
48500 and (Forsome Y) Y is a generalization of X with many examples,
48600
48700 and all examples of Y (ignoring boundary cases) are also examples of
48800 X,
48900
49000 Then conjecture that X is really no more specialized than Y,
49100
49200 and Check the truth of this conjecture on boundary examples of Y,
49300
49400 and see whether Y might itself turn out to be no more specialized
49500 than one of ⊗4its\0 generalizations.
49600
49700 .E
49800
49900 This rule caused AM, while checking examples of odd-primes, to
50000 conjecture that ⊗4all\0 primes were odd-primes.
50100
50200 .BH
50300
50400 λλ If the current task is to Check Examples of concept X,
50500
50600 and (Forsome Y) Y is a specialization of X,
50700
50800 and all examples of X (ignoring boundary cases) are also examples of
50900 Y,
51000
51100 Then conjecture that X is really no more general than Y,
51200
51300 and Check the truth of this conjecture on boundary examples of X,
51400
51500 and see whether Y might itself turn out to be no more general than
51600 one of ⊗4its\0 specializations.
51700
51800 .E
51900
52000 This rule is analogous to the preceding one for generalizations.
52100
52200 .MAH3: BNN;
52300
52400 .BH
52500
52600 λλ When checking boundary examples of a concept C,
52700
52800 ensure that every scrap of C.Defn has been used.
52900
53000 .E
53100
53200 It is often the tiny details in the definition that determine the
53300 precise boundary. Thus we must look carefully to see whether Primes
53400 allows 1 as an example or not. A definition like ``numbers divisible
53500 only by 1 and themselves" includes 1, but this definition doesn't:
53600 ``numbers having precisely 2 divisors". In the LISP program, this
53700 rule contains several hacks (tricks) for checking that the definition
53800 has been stretched to the fullest. For example: if the definition is
53900 of the form ``all x in X such that...", then pay careful attention to
54000 the boundary of X. That is, take the time to access X.Boundary-exs
54100 and X.Boundary-non-exs, and check them against C.Defn.
54200
54300 .BH
54400
54500 λλ When checking examples of C,
54600
54700 Ensure that each example satisfies C.Defn, and each non-example fails
54800 it. The precise member of C.Defn to use can be chosen depending on
54900 the example.
55000
55100 .E
55200
55300 .SYNR2: BNN;
55400
55500 As described earlier in the text, definitions can have descriptors
55600 which indicate what kinds of arguments they might be best for, their
55700 overall speed, etc.
55800
55900
56000 .BH
56100
56200 λλ When checking examples of C,
56300
56400 If an entry e is rejected (i.e., it is seen to be not an example of C
56500 after all), then remove e from C.Exs and consider inserting it on the
56600 Boundary non-examples facet of C.
56700
56800 .E
56900
57000 There is a complicated$$ Not necessarily sophisticated. First, AM
57100 accesses the Worth of C. From this it determines how many boundary
57200 non-examples C deserves to keep around (and how many total list cells
57300 it merits). AM compares these quotas with the current number of (and
57400 size of) entries already listed on C.bdy-non-exs. The degree of need
57500 of another entry there then sets the ``odds" for insertion versus
57600 forgetting. Finally a random number is computed, and the odds
57700 determine what range it must lie in for e to be remembered. $
57800 algorithm for deciding whether to forget e entirely or to keep it
57900 around as a close but not close enough kind of example.
58000
58100 .BH
58200
58300 λλ When checking examples of C,
58400
58500 After an entry e has been verified as a bone fide example of C,
58600
58700 Check whether e is also a valid example of some direct specialization
58800 of C.
58900
59000 If it is, then remove it from C.Exs, and consider adding it to the
59100 examples facet of that specialization, and suggest the task of
59200 Checking examples of that specialization.
59300
59400 .ES
59500
59600 .BH
59700
59800 λλ When checking examples of C,
59900
60000 If an entry e is rejected,
60100
60200 Then check whether e is nevertheless a valid example of some
60300 generalization of C.
60400
60500 If it is, consider adding it to that concept's boundary-examples
60600 facet, and consider adding it to the boundary non-examples facet of
60700 C.
60800
60900 .E
61000
61100 This is similar to the preceding rule.
61200
61300
61400 .BH
61500
61600 λλ When checking non-examples of C, including boundary non-examples,
61700
61800 Ensure that each one fails a definition of C. Otherwise, transfer it
61900 to the boundary examples facet of C.
62000
62100 .ES
62200
62300 .BH
62400
62500 λλ When checking non-examples of C, including boundary non-examples,
62600
62700 After an entry e has been verified as a bone fide non-example of C,
62800
62900 Check whether e is also a non-example of some direct generalization
63000 of C.
63100
63200 If it is, then remove it from C.Non-Exs, and consider adding it to
63300 the non-examples facet of that generalization, and suggest the task
63400 of Checking examples of that generalization.
63500
63600 .ES
63700
63800 .BH
63900
64000 λλ When checking (boundary) non-examples of C,
64100
64200 If an entry e is rejected, that is if it turns out to be an example
64300 of C after all,
64400
64500 Then check whether e is nevertheless a non-example of some
64600 specialization of C.
64700
64800 If it is, consider adding it to that concept's boundary non-examples
64900 facet.
65000
65100 .E
65200
65300 This is similar to the preceding rule.
65400
00100 . ASSSEC(Heuristics for the Conjecs facet of Any-concept)
00200
00300
00400 .HH(Any-concept . Conjecs,Fillin)
00500
00600 When the task is to look around and find conjectures dealing with
00700 concept C, the following general rules may be useful.
00800
00900 .BH
01000
01100 λλ If there is an analogy from X to C, and a nice item in X.Conjecs,
01200 formulate and test the analogous conjecture for C.
01300
01400 .E
01500
01600 Since an analogy is not much more than a set of substitutions,
01700 formulating the `analogous conjecture' is almost a purely syntactic
01800 transformation.
01900
02000 .BH
02100
02200 λλ Examine C.Exs for regularities.
02300
02400 .E
02500
02600 What mysteries are lurking in the LISP code for ⊗4this\0 rule, you
02700 ask? Nothing but a few special-purpose hacks and a few ultra-general
02800 hacks. Here is a slightly more specific rule for you seekers:
02900
03000 .BH
03100
03200 λλ Look at C.Exs. Pick one element at random. Write down statements
03300 true about that example e. Include a list of all concepts of which it
03400 is an example, all Interests features it satisfies, etc.
03500
03600 Then check each conjecture on this list against all other known
03700 examples of C. If any example (except a boundary example) of C
03800 violates a conjecture, discard it.
03900
04000 Take all the surviving conjectures, and eliminate any which trivally
04100 follow from other ones.
04200
04300 .E
04400
04500 This is a common way AM uses: induce a conjecture from one example
04600 and test it on all the rest. A more sophisticated approach might be
04700 to induce it by using a few examples simultaneously, but I haven't
04800 thought of any nontrivial way to do that. The careful reader will
04900 perceive that most of the conjectures AM will derive using this
05000 heuristic will be of the form ``X is unexpectedly a specialization of
05100 Y", or ``X is unexpectedly an example of Y", etc. Indeed, most of
05200 AM's conjectures are really that simple syntactically.
05300
05400 .BH
05500
05600 λλ Formulate a parameterized conjecture, a ``template", which gets
05700 slowly specialized or instantiated into a definite conjecture.
05800
05900 .E
06000
06100 AM has only a few trivial methods for doing this (e.g., introduce a
06200 variable initially and find the constant value to plug in there
06300 later). As usual, they will be omitted here, and the author
06400 encourages some research in this area, to turn out a decent set of
06500 general rules for accomplishing this hypothesis template
06600 instantiation. The best effort to date along these lines, in one
06700 specific sophisticated scientific field, is that of META-DENDRAL
06800 [Buchanan].
06900
07000 .HH(Any-concept . Conjecs,Check)
07100
07200 .BH
07300
07400 λλ If a universal conjecture (For all X's, ...) is contradicted by
07500 empirical data, gather the data together and try to find a regularity
07600 in those exceptions.
07700
07800 If this succeeds, give the exceptions a name N (if they aren't
07900 already a concept), and rephrase the conjecture (For all X's which
08000 are not N's...). Consider making X-N a new concept.
08100
08200 .E
08300
08400 Again note how ``active" this little checking rule can be. It can
08500 patch up nearly-true conjectures, examine data, define new concepts,
08600 etc.
08700
08800 .BH
08900
09000 λλ After verifying a conjecture for concept C,
09100
09200 See if it also holds for related concepts (e.g., a generalization of
09300 C).
09400
09500 .ES
09600
09700
09800 There are of course bookeeping details not explicitly shown above,
09900 which are present in the LISP program. For example, if conjecture X
10000 is true for all specializations of C, then it must be added to
10100 C.Conjecs and removed from the Conjecs facets of each specialization
10200 of C.
10300
10400
10500 .HH(Any-concept . Conjecs,Suggest)
10600
10700 .BH
10800
10900 λλ If X is probably related to Y, but no definite connection is
11000 known,
11100
11200 It's worthwhile looking for a specific conjecture tying X and Y
11300 together.
11400
11500 .E
11600
11700 How might AM know that X and Y are only ⊗4probably\0 related? X and
11800 Y may play the same role in an analogy (e.g., the singleton bag ``(T)``
11900 and ``any typical singleton bag" share many properties), or they may
12000 both be specializations of the same concept Z (e.g., two kinds of
12100 numbers), or they may both have been created in the same unusual way
12200 (e.g., Plus and Times and Exponentiation are all creatable by
12300 ⊗4repeating\0 another operation).
12400
12500
12600 .HH(Any-concept . Conjecs,Interest)
12700
12800 .BH
12900
13000 λλ A conjecture about X is interesting if X is very interesting.
13100
13200 .ES
13300
13400 .BH
13500
13600 λλ A nonconstructive existence conjecture is interesting.
13700
13800 .E
13900
14000 Thus the unique factorization theorem is judged to be interesting
14100 because it merely guarantees that some factoring will be into primes.
14200 If you give an algorithm for that factoring, then the theorem
14300 actually loses its mystique and (according to this rule) some of its
14400 value. But it increases in value due to the next rule.
14500
14600 .BH
14700
14800 λλ A constructive existence conjecture is interesting if it is
14900 frequently used.
15000
15100 .ES
15200
15300 .BH
15400
15500 λλ A conjecture C about X is interesting if the origin and the
15600 verification of C for each specialization of X was quite independent
15700 of each other, and preceded C's being noticed applicable to all X's.
15800
15900 .E
16000
16100 This would be even more striking if ⊗4proof\0 techniques were known,
16200 and each specialized case had a separate kind of proof. Many number
16300 theory results are like this, where there exists a general proof only
16400 for numbers bigger than 317, say, and all smaller numbers are simply
16500 checked individually to make sure they satisfy the conjecture.
16600 Category theory is built upon practically nothing but this heuristic.
16700
16800
00100 . ASSSEC(Heuristics for the Analogies facet of Any-concept)
00200
00300 .HH(Any-concept . Analogies,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in conjectures involving concept C, where C is analogous
00800 to D,
00900
01000 Consider the analogue of each conjecture involving D.
01100
01200 .ES
01300
01400 .BH
01500
01600 λλ If the current task involves a specific analogy, and the request
01700 is to find more conjectures,
01800
01900 Then consider the analog of each interesting conjecture about any
02000 concept involved centrally in the analogy.
02100
02200 .E
02300
02400 That is, this rule suggests applying the preceding rule to each
02500 concept which is central to the given analogy. The result is a flood
02600 of new conjectures. There is a tradeoff (explicitly taken into
02700 account in the LISP version of this rule) between how interesting a
02800 conjecture has to be, and how centrally a concept has to fit into the
02900 analogy, in order to determine what resources AM should be willing to
03000 expend to find the analogous conjecture. Note that this is not a
03100 general suggestion of what to do, but a specific strategy for
03200 enlarging the analogy itself. If the new conjecture is verified, then
03300 not only would it be entered under some Conjecs facet, but it would
03400 also go to enlarging the data structure which represents the analogy.
03500
03600 .BH
03700
03800 λλ Let the analogy suggest how to specialize and generalize each
03900 concept into what is at least the analog of a known, very interesting
04000 concept.
04100
04200 .E
04300
04400 Like the last rule, this one simply says to use the analogy itself as
04500 the ``reason" for exploring certain new entities, in this case new
04600 concepts. When the Bags↔Numbers analogy is made, AM notices that
04700 Singleton bags and Empty bags are two interesting, extreme
04800 specializations of Bags. The above rule then allows AM to construct
04900 and study what we know and love as the numbers one and zero. The
05000 analogy is flawed because there is only one ``one", although there are
05100 many different singleton bags. But just as singletons and empty bags
05200 have special properties under bag operations, so do 0,1 under numeric
05300 operations. This was one case where an analogy paid off handsomely.
05400
05500 .BH
05600
05700 λλ If it is desired to have an analogy between concepts X and Y, then
05800 look for two already-known analogies between X↔Z and Z↔Y, for any Z.
05900
06000 If found, compose the two analogies and see if the resultant analogy
06100 makes sense.
06200
06300 .ES
06400
06500 Since the analogies are really just substitutions, composing them has
06600 a familiar, precise meaning. This rule was never really used by AM,
06700 due to the paucity of analogies. The user can push AM into creating
06800 more of them, and ultimately using this rule. A chain from X↔Z↔Y↔X
06900 can be found which presents a new, bizarre analogy from X to itself.
07000
07100 .HH(Any-concept . Analogies,Suggest)
07200
07300 .BH
07400
07500 λλ If an analogy is strong, and one concept has a very interesting
07600 universal conjecture C (For all x in B...), but the analog conjecture
07700 C' is false,
07800
07900 Then it's worth constructing the set of items in B' for which the
08000 conjecture holds. It's perhaps even more interesting to isolate the
08100 set of exceptional elements.
08200
08300 .E
08400
08500 With the Add↔Times analogy, it's true that all numbers n>1 can be
08600 represented as the sum of two other numbers (each of them smaller
08700 than n), but it is ⊗4not\0 true that all numbers (with just a couple
08800 exceptions) can be represented as the product of other (hence
08900 smaller) numbers. The above rule has AM define the set of numbers
09000 which can/can't be so represented. These are just the composite
09100 numbers and the set of primes. This second way of encountering
09200 primes was very unexpected -- both by AM and by the author. It
09300 expresses the deep fact that one difference between Add and Times is
09400 the presence of primes only for multiplication. At the time of its
09500 discovery, AM didn't appreciate this fully of course.
09600
09700 .PRIM2: BNN;
09800
09900 .PRIM2P: PAGE;
10000
10100 .BH
10200
10300 λλ If space is tight, and no use of the analogy has ever been made,
10400 and it is very old, and it takes up a lot of space,
10500
10600 Then it is permissable to forget it without a trace.
10700
10800 .ES
10900
11000 .BH
11100
11200 λλ If two valuable conjectures are syntactically identical, and can
11300 be made identical by a simple substitution, then tentatively consider
11400 the analogy which is that very substitution.
11500
11600 .E
11700
11800 Thus the associative/commutative property of Add and Times causes
11900 them to be tied together in an analogy, because of this rule.
12000
12100 .BH
12200
12300 λλ If an analogy is very interesting and very complete,
12400
12500 Then spend some time refining it, looking for small exceptions. If
12600 none are found, see whether the two situations are genuinely
12700 isomorphic.
12800
12900 .ES
13000
13100 .BH
13200
13300 λλ If concepts X and Y are analogous, look for analogies between
13400 their specializations, or between their generalizations.
13500
13600 .E
13700
13800 This rule is not used much by AM, although the author thought it
13900 would be.
14000
14100
14200
14300 .HH(Any-concept . Analogies,Interest)
14400
14500 .BH
14600
14700 λλ An analogy which has no discrepancies whatsoever is not as
14800 interesting as a slightly flawed analogy.
14900
15000 .ES
15100
15200 .BH
15300
15400 λλ An analogy is interesting if it associates (for the first time)
15500 two concepts which are each unusally fully filled out (having many
15600 conjectures, many examples, many interest features, etc.).
15700
15800 .ES
15900
00100 . ASSSEC(Heuristics for the Genl/Spec facets of Any-concept)
00200
00300 .HH(Any-concept . Genl/Spec,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in specializations of X, if it was very easy to find
00800 examples of X,
00900
01000 Grab some features which would indicate than an X was interesting
01100 (some entries from X.Interest, or more remote Interest predicates
01200 garnered by rippling), and conjoin them onto the definition of X,
01300 thereby creating a new concept.
01400
01500 .E
01600
01700 Here's one instance where the above rule was used: It was so easy for
01800 AM to produce examples of sets that it decided to specialize that
01900 concept. The above rule then plucked the interestingness feature ``all
02000 pairs of members satisfy the same rare predicate" and conjoined it to
02100 the old definition of Sets. The new concept, Interesting-sets,
02200 included all singletons (because all pairs of members drawn from a
02300 singleton satisfy the predicate Equal) and empty sets.
02400
02500 .BH
02600
02700 λλ To fill in generalizations of concept X,
02800
02900 Take the definition e, and replace it by a generalization of e. If e
03000 is a concept, use e.Genl; if e is a conjunction, then remove a
03100 conjunct or generalize$$ i.e., recur. $ a conjunct; if e is a
03200 disjunction, then add a disjunct or generalize a disjunct; if e is
03300 negated, then specialize the negate; if e is an example of E, then
03400 replace e by ``any example of E"; if e satisfies any property P, then
03500 replace e by ``anything satisfying P"; if e is a constant$$ Of course
03600 it's unlikely that a concept is defined simply as a constant, but the
03700 preceding footnote shows that this little program can be entered
03800 recursively, being fed a sub-expression of the definition. $, then
03900 replace e by a new variable (or an existing one) which could assume
04000 value e; if e is a variable, then enlarge its scope of possible
04100 bindings.
04200
04300 .E
04400
04500 .SEZ3: BNN;
04600
04700 This rule contains a bag of tricks for generalizing any LISP
04800 predicate, the definition of any concept. They are all ⊗4syntactic\0
04900 tricks, however.
05000
05100 .BH
05200
05300 λλ To fill in generalizations of concept X, If some conjecture exists
05400 about ``all X's and Y's" or ``in X or Y", for some other concept Y,
05500
05600 Create a new concept, a generalization of both X and Y, defined as
05700 their disjunction.
05800
05900 .E
06000
06100 This rule contains another trick for generalizing any concept,
06200 although it is more meaningful, more semantic than the previous
06300 rule's tricks. Many theorems are true about numbers with 1 or 2
06400 divisors, so this might be one reasonable way to generalize
06500 Numbers-with-α1-divisor into a new useful$$ at least, several
06600 theorems will be stated more concisely using this new concept:
06700 Numbers with 1 or 2 divisors. $ concept.
06800
06900 .BH
07000
07100 λλ To fill in generalizations of concept X,
07200
07300 If other generalizations G1, G2 of X exist but are TOO general,
07400
07500 Create a new concept, a generalization of X and a specialization of
07600 both G1 and G2, defined as the conjunction of G1 and G2's
07700 definitions.
07800
07900 .E
08000
08100 .MAH4: BNN;
08200
08300 Thus when AM generalizes Reverse-all-levels into Reverse-top-level
08400 and Reverse-first-element, the above rule causes AM to create a new
08500 operation, which reverses the top level and which reverses the CAR$$
08600 also the CAR of the CAR, etc., until a non-list is encountered. $ of
08700 the original list. While not particularly useful, the reader should
08800 observe that it is in fact midway in generality between the original
08900 Reverse function and the first two generalizations.
09000
09100 .BH
09200
09300 λλ To fill in specializations of concept X,
09400
09500 Take the definition e, and replace it by a specialization of e. If e
09600 is a concept, use e.Genl; if e is a disjunction, then remove a
09700 disjunct or specialize a disjunct; if e is a conjunction, then add a
09800 conjunct or specialize a conjunct; if e is negated, then generalize
09900 the negate; if e is ``any example of E", then replace e by a
10000 particular example of E; if e is ``anything satisfying P", then
10100 replace e by a particular satisfier of P; if e is a variable, then
10200 replace it by a well-chosen constant or restrict its scope.
10300
10400 .E
10500
10600 This rule contains a bag of tricks for specializing any LISP
10700 predicate, the definition of any concept. They are all ⊗4syntactic\0
10800 tricks, however. Note that the Lisp code for this rule will typically
10900 call itself (recur) in order to specialize small pieces of the
11000 original definition.
11100
11200 .BH
11300
11400 λλ To fill in specializations of concept X, If some conjecture exists
11500 about ``all X's which are also Y's" or ``in X and Y", for some other
11600 concept Y,
11700
11800 Create a new concept, a specialization of both X and Y, defined as
11900 their conjunction.
12000
12100 .E
12200
12300 This rule contains another trick for specializing any concept,
12400 although it is more meaningful, more semantic than the previous
12500 rule's tricks. Many theorems about primes contain the condition
12600 ``p>2"; i.e., they are really true about primes which are odd. So this
12700 might be one reasonable way to specialize Primes into a new concept:
12800 by conjoining the definitions of Primes and Odd-numbers, into the new
12900 concept Odd-primes. Here's another usage of this rule: If AM had
13000 originally defined Primes to include `1', then the frequency of
13100 conjectures where 1 was an exception would trigger this rule to
13200 define Primes more normally (p⊗6≥\02).
13300
13400 .BH
13500
13600 λλ To fill in specializations of concept X,
13700
13800 If other specializations S1, S2 of X exist but are TOO restrictive to
13900 be interesting,
14000
14100 Create a new concept, a specialization of X and a generalization of
14200 both S1 and S2, defined as the disjunction of S1 and S2's
14300 definitions.
14400
14500 .ES
14600
14700 .BH
14800
14900 λλ To fill in generalizations of concept X, when a recursive
15000 definition of X exists,
15100
15200 If the definition contains two conjoined recursive calls, replace
15300 them by a disjunction or eliminate one call entirely.
15400
15500 If there is only one recursive call, disjoin a second call, this one
15600 on a different destructive function applied to the original argument.
15700 If the original destructive function is one of {CAR,CDR}, then let
15800 the new one be the other member of that pair.
15900
16000 .E
16100
16200 AM uses the first part of this rule to turn Equal-lists into two
16300 variants of Same-length-as. The second part, while surprisingly
16400 unused, could work on this definition of ⊗3MEMBER: ``λ (x,L) LISTP(L)
16500 and: [x=CAR(L) or MEMBER(x,CDR(L))]``\0, which is just ``membership at
16600 the top level of", or ⊗6ε\0, and transform it into this one of
16700 ⊗3MEM\0, which represents membership at ⊗4any\0 depth: ``⊗3λ(x,L)
16800 LISTP$$ The Interlisp function LISTP(L) tests whether or not L is a
16900 (nonnull) list. $⊗3(L) and: [x=CAR(L) or MEM(x,CDR(L)) or
17000 MEM(x,CAR(L))]⊗1". The rule noticed a recursive call on CDR(L), and
17100 simply disjoined a recursive call on CAR(L).
17200
17300 .BH
17400
17500 λλ To fill in specializations of concept X, when a recursive
17600 definition of C exists,
17700
17800 If the definition contains two disjoined recursive calls, replace
17900 them by a conjunction or eliminate one call entirely.
18000
18100 If there is only one recursive call, conjoin a second on another
18200 destructive function applied to the original argument. Often the two
18300 recursions will be on the CAR and the CDR of the original argument to
18400 the predicate which is the definition for X.
18500
18600 .E
18700
18800 This is closely related to the preceding rule. Just as it turned the
18900 concept of `element of' into the more general one of `membership at
19000 any depth', the above rule can specialize the definition of
19100 ⊗3MEMBER\0 into this one, called ⊗3AMEM: ``λ (x,L) LISTP(L) and:
19200 [x=CAR(L) or: [AMEM(x,CDR(L)) and AMEM(x,CAR(L))]]``\0.$$ This operation is
19300 almost impossible to explain verbally. AMEM(x,L) means that x is an element of L,
19400 and for each member M of L before the x, M is an ordered
19500 structure and x is an element of M,
19600 and for each member N of M before the x which is inside M,... etc.
19700 E.g., <[x] [ ⊗6<\0<x a b> <x> x d e⊗6>\0 <x f> x g h ] [<x i> x j] x k [l] m>. $
19800
19900 .SELECT 1;
20000
20100 .BH
20200
20300 λλ To fill in specializations of concept X,
20400
20500 Find,, within a definition of X (at even parity of NOT's), an
20600 expression of the form ``For some x in X, P(x)``, and replace it either
20700 by ``For all x in X, P(x)``, or by P(x⊗7↓o\0).
20800
20900 .E
21000
21100 .QUADRULE: BNN;
21200
21300 Thus ``sets, all pairs of whose members satisfy SOME interesting
21400 predicate" gets specialized into ``sets, all pairs of whose members
21500 satisfy Equality". The same rule, with ``even parity" replaced by
21600 ``odd parity", is useful for ⊗4generalizing\0 a definition. This rule
21700 is really 4 separate rules, in the LISP program. The same rule, with
21800 the transformations going in the opposite direction, is also used for
21900 generalizing. The same rule, with the transformations reversed and
22000 the parity reversed, is used for specializing a definition. Here is
22100 that doubly-switched rule:
22200
22300 .BH
22400
22500 λλ To fill in specializations of concept X,
22600
22700 Find within a definition of X (at odd parity of NOT's) an expression
22800 of the form ``For all x in X, P(x)``, and replace it either by ``For
22900 some x in X, P(x)``, or by P(x⊗7↓o\0). Or replace ``P(αα)``, where αα
23000 is a constant, by ``For some x in A, P(x)`` where A is a concept of
23100 which αα is one example.
23200
23300 .ES
23400
23500 .BH
23600
23700 λλ When creating in a specialization S of concept C,
23800
23900 Note that S.Genl should contain C, and that C.Spec should contain S.
24000
24100 .E
24200
24300 The analogous rule exists, in which all spec and genl are switched.
24400
24500
24600
24700 .HH(Any-concept . Genl/Spec,Suggest)
24800
24900 .BH
25000
25100 λλ After creating a new specialization S of concept C,
25200
25300 Explicitly look for ties between S and other known specializations of
25400 C.
25500
25600 .E
25700
25800 For example, after AM defines the new concept of
25900 Numbers-with-3-divisors, it looks around for ties between that kind
26000 of number and other kinds of numbers.
26100
26200 .BH
26300
26400 λλ After creating a new generalization G of concept C,
26500
26600 Explicitly look for ties between G and other close generalizations of
26700 C.
26800
26900 .E
27000
27100 For example, AM defined the new predicates Same-size-CARs and
27200 Same-size-CDRs$$ Two lists satisfy Same-size-CDRs iff they have the
27300 same number of members. Two lists satisfy Same-size-CARs iff (when
27400 written out in standard LISP notation) they have the same number of
27500 initial left parentheses and also have the same first identifier
27600 following that last initial left parenthesis. $ as two
27700 generalizations of Equality. The above rule then suggested that AM
27800 explicitly try to find some connection between these two new
27900 predicates. Although ⊗4AM\0 failed, Don Knuth (using a similar
28000 heuristic, perhaps) also looked for a connection, and found one: it
28100 turns out that the two predicates are both ways of defining the
28200 relation we intuitively understand as ``having the same length as".
28300
28400 .BH
28500
28600 λλ After creating a new specialization S of concept C,
28700
28800 Consider looking for examples of S.
28900
29000 .E
29100
29200 This has to be said explicitly, because all too often a concept is
29300 specialized into vacuousness.
29400
29500
29600 .BH
29700
29800 λλ After creating a new generalization G of concept C,
29900
30000 Consider looking for non-examples of G.
30100
30200 .E
30300
30400 This has to be said explicitly, because all too often a concept is
30500 generalized into vacuous universality. This rule is less useful to AM
30600 than the preceding one.
30700
30800 .BH
30900
31000 λλ If concept C possesses some very interesting property lacked by
31100 one of its specializations S,
31200
31300 Then considering creating a concept intermediate in specialization
31400 between C and S, and see whether that possesses the property.
31500
31600 .E; INTERMES: BNN;
31700
31800 This rule will trigger whenever a new generalization or
31900 specialization is created.
32000
32100 .BH
32200
32300 λλ If concept S is now very interesting, and S was created as a
32400 specialization of some earlier concept C,
32500
32600 Give extra consideration to specializing S, and to specializing
32700 concept C again (but in different ways than ever before).
32800
32900 .E
33000
33100 The next rule is the analog of the preceding one. They incorporate
33200 tiny bits of the strategies of hill-climbing and learning from one's
33300 successes.
33400
33500 .BH
33600
33700 λλ If concept G is now very interesting, and G was created as a
33800 generalization of some earlier concept C,
33900
34000 Give extra consideration to generalizing G, and to generalizing C in
34100 other ways.
34200
34300 .E
34400
34500 The analogous rules exist, for concepts that have become so boring
34600 they've just been discarded:
34700
34800 .BH
34900
35000 λλ If concept X proved to be a dead-end, and X was created as a
35100 generalization of (specialization of) some earlier concept C,
35200
35300 Give less consideration to generalizing (specializing) X, and to
35400 generalizing (specializing) C in other ways in the future.
35500
35600 .ES
35700
35800
35900
36000
36100 .HH(Any-concept . Genl/Spec,Check)
36200
36300 .BH
36400
36500 λλ When checking a generalization G of concept C,
36600
36700 Specifically test to ensure that G is not equivalent to C.
36800
36900 The easiest way is to examine the non-examples (especially boundary
37000 non-examples) of C, and look for one satisfying G; or examine the
37100 examples of G (esp. boundary) and look for one failing to satisfy C.
37200
37300 If they appear to be the same concept, look carefully at G. Are there
37400 any specializations of G whose examples have never been filled in? If
37500 so, then by all means suggest looking for such concepts' examples
37600 before concluding that G and C are really equivalent.
37700
37800 .INDENT 8,16,0
37900
38000 If they are the same, then replace one by a conjecture.
38100
38200 If they are different, make sure that some boundary non-example of C
38300 (which is an example of G) is explicitly stored for C.
38400
38500 .E
38600
38700 .RESERVE: BNN;
38800
38900 .RESERVEP: PAGE;
39000
39100 This rule makes sure that AM is not deluding itself. When AM
39200 generalizes Numbers-with-α1-divisor into
39300 Numbers-which-equal-their-no-of-divisors, it still hasn't gotten past
39400 the singleton set {1}. The conjecture in this case would be ``⊗4The
39500 only number which equals its own number of divisors is 1\0".
39600 Typically, when a generalization G of C turns out to be equivalent to
39700 C, there is theorem lurking around, of the form ``All G's also satisfy
39800 this property...", where the property is the ``extra" constraint
39900 present in C's definition but absent from G's. This rule also was
40000 used when AM had just found some examples of Sets. AM almost believed
40100 that all Unordered-Structures were also Sets, but the last main
40200 clause of the rule had AM notice that Bags is a specialization of
40300 Unordered-structures, and that the latter concept had never had any
40400 of its examples filled in. As a result, AM printed out this message:
40500 ``Almost concluded that Unordered-structures are also always Sets.
40600 But will wait until examples of Bags are found. Perhaps some Bags
40700 will not be Sets." In fact, examples of Bags are soon found, and they
40800 aren't sets.
40900
41000 .BH
41100
41200 λλ When checking a specialization S of concept C,
41300
41400 Specifically test to ensure that S is not equivalent to C.
41500
41600 .INDENT 8,16,0
41700
41800 If they are the same, then replace one by a conjecture.
41900
42000 If they are different, make sure that some boundary example of C
42100 (which is not an example of S) is explicitly stored for C.
42200
42300 .E
42400
42500 This rule is similar to the preceding one. If adding a new constraint
42600 P to the definition doesn't change the concept C, then there is
42700 probably a theorem there of the form ``All C's also satisfy constraint
42800 P".
42900
43000 .BH
43100
43200
43300 λλ When checking a specialization S of a specialization X of a
43400 concept C,
43500
43600 if there exist other specs. of specs. of C,
43700
43800 then ensure that none of them are the same as S. This is especially
43900 worthwhile if the specializing operators in each case were the same
44000 but reversed in order.
44100
44200 .E
44300
44400 .SOFSC: BNN;
44500
44600 Thus we can add a constraint to C and collapse the first two
44700 arguments, or we can collapse the arguments and add the constraint;
44800 either way, we get to the same very specialized new concept. The
44900 above rule helps detect those accidental duplicates. E.g.,
45000 Coalesced-Dom=Ran-Compositions are really the same as
45100 Dom=Ran-Coalesced-Compositions, and this rule would suspect that they
45200 might be.
45300
45400 .BH
45500
45600 λλ When checking the Genl or Spec facet entries for concept C,
45700
45800 ensure that C.Genl and C.Spec have no common member Z. If they do,
45900 then conjecture that C and Z are actually equivalent.
46000
46100 .E; ONCE TURN ON ``{}``;
46200
46300 In fact, this rule actually ensures that Generalizations(C) does not
46400 intersect Specializations(C). If it does, a whole `cycle' of concepts
46500 exists which can be collapsed into one single concept. See also rule
46600 {[3]GSCHAIN}, below.
46700
46800
46900
47000 .HH(Any-concept . Genl/Spec,Interest)
47100
47200
47300 .BH
47400
47500 λλ A generalization of X is interesting if all the previously-known
47600 boundary non-examples are now boundary examples of the concept.
47700
47800 .E
47900
48000 A check is included here to ensure that the new concept was not
48100 simply defined as the closure of the old one.
48200
48300 .BH
48400
48500 λλ A specialization of X is interesting if all the previously-known
48600 boundary examples are now boundary non-examples of the new
48700 specialized concept.
48800
48900 .E
49000
49100 A check is included here to ensure that the new concept was not
49200 simply defined as the interior of the old one.
49300
49400 .BH
49500
49600 λλ If C1 is a generalization of C2, which is a generalization of
49700 C3,..., which is a generalization of Cj, and it has just been learned
49800 that Cj is a generalization of C1,
49900
50000 Then all the concepts C1,...,Cj are equivalent, and can be merged,
50100 and the combined concept will be much more interesting than any
50200 single one, and the interestingness of the new composite concept
50300 increases rapidly with j.
50400
50500 .E; GSCHAIN: BNN; ONCE TURN ON ``{}``;
50600
50700 The Lisp code has the new interest value be computed as the maximum
50800 value of the old concepts, plus a bonus which increases like the
50900 square of j. This is similar to rule number {[3]REDERIVE}. A rule
51000 just like the preceding one exists, with `Specialization' substituted
51100 everywhere for `Generalization'. Thus a closed loop of Spec links
51200 constitutes a demonstration that all the concepts in that loop are
51300 equivalent. These rules were used more frequently than expected.
51400
00100 . ASSSEC(Heuristics for the View facet of Any-concept)
00200
00300 .HH(Any-concept . View,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in View facet entries for X,
00800
00900 Find an interesting operation F whose range is X,
01000
01100 and indicate that any member of Domain(F) can be viewed as an X just by
01200 running F on it.
01300
01400 .E
01500
01600 While trying to fill in the View facet of Even-nos, AM used this rule. It
01700 located the operation Doubling, whose domain is Numbers and whose range is
01800 Even-nos. Then the rule created a new entry: ``to view any number as if it were
01900 an even number, double it". This is a twisted affirmation of the standard
02000 correspondence
02100 between natural numbers and even natural numbers.
02200
02300
00100 . ASSSEC(Heuristics for the In-dom/ran-of facets of Any-concept)
00200
00300 .HH(Any-concept . In-dom-of/In-ran-of,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in entries for the In-dom-of facet of concept X,
00800
00900 Ripple down the tree of concepts, starting at Active, to empirically
01000 determine which active concepts can be run on X's.
01100
01200 .E
01300
01400 This can usually be decided by inspecting the Domain/range facets of
01500 the Active concepts. Occasionally, AM must actually try to run an
01600 active on sample X's, to see whether it fails or returns a value.$$
01700 One key feature of Lisp which permits this to be done is the Errorset
01800 feature. $
01900
02000 .BH
02100
02200 λλ To fill in the In-ran-of facet of concept X,
02300
02400 Ripple down the tree of concepts, starting at Active, to empirically
02500 determine which active concepts can be run to yield X's.
02600
02700 .E
02800
02900 This can usually be decided by inspecting the Domain/range facets of
03000 the Active concepts. Occasionally, AM inspects known examples of some
03100 Active concept, to see if any of the results are X's.
03200
03300 .BH
03400
03500 λλ While filling in entries for the In-dom-of facet of X,
03600
03700 Look especially carefully for Operations which transform examples and
03800 non-examples into each other;
03900
04000 This is even better if the operation pushes boundary exs/non-exs
04100 `across the boundary'.
04200
04300 .E
04400
04500 This was used to note that Insert and Delete had a lot to do with the
04600 concept of Singleton.
04700
00100 . ASSSEC(Heuristics for the Definition facet of Any-concept)
00200
00300 .HH(Any-concept . Defn,Suggest)
00400
00500 .BH
00600
00700 λλ If there are no known definitions for concept X,
00800
00900 Then it is crucial that AM spend some time looking for such
01000 definitions.
01100
01200 .E
01300
01400 This situation might occur if only an Algorithm is present for some
01500 concept. In that case, the above rule would suggest a new,
01600 high-priority task, and AM would then twist the algorithm into a
01700 (probably very inefficient) definition. A much more serious
01800 situation would occur if a concept were specified only by its
01900 Intuition entries (created, e.g., by modifying another concept's
02000 intuitions). In that case, rapidly formulating a precise definition
02100 would be a necessity. Of course, this need never arose, since all
02200 the intuitions were deleted.
02300
02400
02500
02600 .HH(Any-concept . Defn,Check)
02700
02800 .BH
02900
03000 λλ When checking the Definition facet of concept C,
03100
03200 Ensure that each member of C.Exs satisfies all definitions present,
03300 and each non-example fails all definitions. If there is one
03400 dissenting definition, modify it, and move the offending example to
03500 the boundary.
03600
03700 .E
03800
03900 There is little real ``checking" that can be done to a definition,
04000 aside from internal consistency: If there exist several
04100 suposedly-equivalent definitions, then AM can at least ensure they
04200 agree on the known examples and non-examples of the concept. If the
04300 Intuitions facets were permitted, then each definition could be
04400 checked for intuitive appeal.
04500
04600 .BH
04700
04800 λλ When checking the Definition facet of concept C,
04900
05000 Try to find and eliminate any redundant constraints, try to find and
05100 eliminate any circularity, check that any recursion will terminate.
05200
05300 .E
05400
05500 Here are the other few tricks that AM knows for ``checking" a
05600 definition. For each clause in the rule above, AM has a very limited
05700 ability to detect and patch up ``bugs" of that sort. Checking that
05800 recursion will terminate, for example, is done by examining the
05900 argument to the recursive call, and verifying that it contains (at
06000 some level before the original argument) an application of a LISP
06100 function on Destructive-LISP-functions-list. There is no intelligent
06200 inference that is going on here, and for that reason the process is
06300 not even mentioned within the body of this document.
06400
06500 .A4ANYBLAST: SSSECNUM;
06600
06700 .A4ANYBLASTP: PAGE;
06800
00100 .ASSECP(Heuristics for dealing with any Active concept)
00200
00300 All the rules below are applicable to tasks which involve operations,
00400 predicates, relations, functions, etc. In short, they apply to all
00500 the concepts AM knows about which involve ⊗4doing\0 something, which
00600 involve action.
00700
00800 .HH(Active,Fillin)
00900
01000
01100 .BH
01200
01300 λλ If the current task is to fill in examples of the activity F,
01400
01500 One way to get them is to run F on randomly chosen examples of the
01600 domain of F.
01700
01800 .E
01900
02000 .RUNOP: BNN;
02100
02200 Thus, to find examples of Equality, AM repeatedly executed
02300 Equality.Alg on randomly chosen pairs of objects. AM found examples
02400 of Compositions by actually picking a pair of operations at random
02500 and trying to compose them. Of course, most such ``unmotivated"
02600 compositions turned out to be uninteresting.
02700
02800 .BH
02900
03000 λλ While filling in examples of the activity F, by running F.Algs on
03100 random arguments from F.Domain,
03200
03300 It is worth the effort to specifically include extreme or boundary
03400 examples of the domain of F, among the arguments on which F.Algs is
03500 run.
03600
03700 .ES
03800
03900 .BH
04000
04100 λλ To fill in a Domain entry for active concept F,
04200
04300 Run F on various entities, rippling down the tree of concepts, to
04400 determine empirically where F seems to be defined.
04500
04600 .E
04700
04800 This may shock the reader, as it sounds dumb and explosive, but the
04900 concepts are arranged in a tree (using Genl links), so the search is
05000 really quite fast. Although this rule is rarely used, it always
05100 seems to give surprisingly good results.
05200
05300 .BH
05400
05500 λλ To fill in generalizations of active F,
05600
05700 Consider just extending F, by enlarging its domain. Revise F.Defn as
05800 little as possible.
05900
06000 .E
06100
06200 Although Equality is initially only for structures, AM extends it
06300 (using the same definition, actually) to a predicate over all pairs
06400 of entities.
06500
06600 .BH
06700
06800 λλ To fill in specializations of active F,
06900
07000 Consider just restricting F, by shrinking its domain. Check F.Defn to
07100 see if some optimization is possible.
07200
07300 .ES
07400
07500 .BH
07600
07700 λλ After an algorithm is known for F, if AM wants a better one,
07800
07900 AM is permitted to ask the user to provide a fast but opaque
08000 algorithm for F.
08100
08200 .E
08300
08400 This was used a few times, especially for inverse functions. A
08500 nontrivial open-ended research problem (*)$$ Following Knuth, we
08600 shall reserve a star ⊗1(*)\0 for those problems which are quite
08700 difficult, which should take the reader roughly 3 full lifetimes to
08800 master. Readers not believing in reincarnation should therefore skip
08900 such problems. $ ⊗1is to collect a body of rules which transform an
09000 inefficient algorithm into a computationally acceptable one.
09100
09200 .BH
09300
09400 λλ If the current task is to fill in boundary (non-)examples of the
09500 activity F,
09600
09700 One way to get them is to run F on randomly chosen boundary examples
09800 and (with proper safeguards) boundary non-examples of the domain of
09900 F.
10000
10100 .E
10200
10300 Proper safeguards are required to ensure that F.Algs doesn't loop or
10400 cause an error when fed a slightly-wrong (slightly-illegal) argument.
10500 In LISP, a timer and an ERRORSET suffice as crude safeguards.
10600
10700 .BH
10800
10900 λλ If the current task is to fill in (boundary) non-examples of the
11000 activity F,
11100
11200 One low-interest way to get them is to run F on randomly chosen
11300 examples of its domain, and then replace the value obtained by some
11400 other (very similar) value. Also, be sure to check that the
11500 resultant i/o pair doesn't accidentally satisfy F.Defn.
11600
11700 .E
11800
11900 The parentheses in the above rule mean that it is really two rules:
12000 for ⊗4boundary\0 non-examples, just change the final value slightly.
12100 For ⊗4typical\0 non-examples, change the result significantly. If
12200 you read the words inside in the parentheses in the IF part, then
12300 read the words inside the parentheses in the THEN part as well,
12400 ⊗4or\0 omit them in both cases.
12500
12600 .DOUBRULE: BNN;
12700
12800
12900
13000 .HH(Active,Check)
13100
13200 .BH
13300
13400 λλ When checking an algorithm for active F,
13500
13600 run that algorithm and ensure that the input/output satisfy F.Defn.
13700
13800 .ES
13900
14000 .BH
14100
14200 λλ When checking a definition d for active concept F,
14300
14400 Run one of its algorithms and ensure that the input/output satisfy d.
14500
14600 .E
14700
14800 This is the converse of the preceding rule. They simply say that the
14900 definition and algorithm facets must be mutually consistent.
15000
15100 .BH
15200
15300 λλ While checking examples or boundary examples of the active concept
15400 F,
15500
15600 Ensure that each input/output pair is consistent with F.Dom/range.
15700
15800 .E
15900
16000 If the domain/range entry is <D1 D2... Dk → R>, and the i/o pair is
16100 <d↓1 d↓2... d↓k , r>, then each component d↓i of the input must be an
16200 example of the corresponding Di, and the output r must be an example
16300 of R.
16400
16500 .BH
16600
16700 λλ When checking examples of the active concept F,
16800
16900 If any argument(s) to F were concepts, tag their In-domain-of facets
17000 with `F'.
17100
17200 If any values produced by F are concepts, tag their In-range-of
17300 facets with `F'.
17400
17500 .E
17600
17700 For example, Restrict(Union) produced Add, at one time in AM's
17800 history. Then the above rule caused `Restrict' to be inserted as a
17900 new entry on Union.In-dom-of and also on Add.In-ran-of.
18000
18100
18200
18300 .HH(Active,Suggest)
18400
18500 .BH
18600
18700 λλ If there are no known algorithms for active concept F,
18800
18900 Then AM should spend some time looking for such algorithms.
19000
19100 .E
19200
19300 This situation might occur if only a Definition is present for some
19400 operation. In that case, the above rule would suggest a new,
19500 high-priority task, and AM would then twist the definition into a
19600 (probably very inefficient) algorithm. The rule below is similar,
19700 for the Domain/range facet:
19800
19900
20000 .BH
20100
20200 λλ If the Domain/range facet of active concept F is blank,
20300
20400 Then AM should spend some time looking for specifications of F's
20500 domain and range.
20600
20700 .ES
20800
20900 .BH
21000
21100 λλ If a Domain of active concept F is encountered frequently, either
21200 within conjectures or as the domain or range of other operations and
21300 predicates,
21400
21500 Then define that Domain as a separate concept, and raise the Worth of
21600 F slightly.
21700
21800 .E
21900
22000 .MAH5: BNN;
22100
22200 The `Domain' here refers to the sequence of components, whose
22300 cartesian product is what is normally referred to in mathematics as
22400 the domain of the operation. This led to the definition of
22500 ``Anything⊗7 x \0Structures", which is the domain of several Insertion
22600 and Deletion operations, Membership testing predicates, etc.
22700
22800 .BH
22900
23000 λλ It is worthwhile to explicitly calculate the value of F for all
23100 distinguished (extreme, boundary, interesting) members of and subsets
23200 of its domain.
23300
23400 .ES
23500
23600 .BH
23700
23800 λλ If some domain component of F has a very interesting
23900 specialization,
24000
24100 Then consider restricting F (along that component) to that smaller
24200 domain.
24300
24400 .E
24500
24600 Note that these last couple rules deal with the image of interesting
24700 domain items. The next rule deals with the inverse image (pre-image)
24800 of unusual range items. We saw earlier in this document (Chapter 2)
24900 how this rule led to the definition of Prime numbers.
25000
25100 .BH
25200
25300 λλ If the range of F contains interesting items, or an interesting
25400 specialization,
25500
25600 Then it is worthwhile to consider their inverse image under F.
25700
25800 .ES
25900
26000 .MAH6: BNN;
26100
26200 .BH
26300
26400 λλ When trying to fill in new Algorithms for Active concept F,
26500
26600 Try to transform any conjectures about F into (pieces of) new
26700 algorithms.
26800
26900 .E
27000
27100 This is one place where a sophisticated body of transformation rules
27200 might be inserted. Others are working on this problem [Burstall &
27300 Darlington 75], and AM only contains a few simple tricks for turning
27400 conjectures into procedures. For example, ``All primes are odd,
27500 except `2'``, is transformed into a more eficient search for primes: a
27600 separate test for x=2, followed by a search through only Odd-numbers.
27700
27800 .BH
27900
28000 λλ After trying in vain to fill in examples of active concept F,
28100
28200 Locate the domain of F, and suggest that AM try to fill in examples
28300 for each component of that domain.
28400
28500 .E
28600
28700 .GOAL1: BNN;
28800
28900 Thus after failing to find examples for Set-union, AM was told to
29000 find examples of Sets, because that could have let the previous task
29100 succeed. There is no recursion here: after the sets are found, AM
29200 will not automatically go back to finding examples of Set-union. In
29300 practice, that task was eventually proposed and chosen again, and
29400 succeeded this time.
29500
29600 .BH
29700
29800 λλ After working on an Active concept F,
29900
30000 Give a slight, ephemeral boost to tasks involving Domain(F): give a
30100 moderate size boost to each task which asks to fill in examples of
30200 that domain/range component, and give a very tiny boost to each other
30300 task mentioning such a concept.
30400
30500 .E
30600
30700 .FROB2: BNN; ONCE TURN ON ``{}``;
30800
30900 This is both a supplement to the more general ``focus of attention"
31000 rule, and a nontrivial heuristic for finding valuable new tasks. It
31100 is the partial converse of rule {[3]FROB1}.
31200
31300
31400
31500 .HH(Active,Interest)
31600
31700 .BH
31800
31900 λλ An active concept F is interesting if there are other operations
32000 with the same domain as F, and if they are (on the average) fairly
32100 interesting. If the other operations' domain is only similar, then
32200 they must be very interesting and have some valuable conjectures tied
32300 to them, if they are to be allowed to push up F's interestingness
32400 rating.
32500
32600 .E
32700
32800 The value of having the same domain/range is the ability to compose
32900 with them. If the domain/range is only similar, then AM can hope for
33000 analogies or for partial compositions.
33100
33200 .BH
33300
33400 λλ An active concept is interesting if it was recently created.
33500
33600 .E
33700
33800 This is a slight extra boost given to each new operation, predicate,
33900 etc. This bonus decays rapidly with time, and thus so will the
34000 overall worth of the concept, unless some interesting property is
34100 encountered quickly.
34200
34300
34400 .BH
34500
34600 λλ An active concept is interesting if its domain is very
34700 interesting.
34800
34900 .E
35000
35100 .IIDOM: BNN; ONCE TURN ON ``{}``;
35200
35300 An important common case of this rule is when the domain is
35400 interesting because all its members are equal to each other. The
35500 corresponding statement about ⊗4ranges\0 does exist, but only
35600 operations can be said to have a specific range (not, e.g.
35700 Predicates). Therefore, the `range' rule is listed under
35800 Operation.Interest, as rule number {[3]IRAN}.
35900
00100 .ASSECP(Heuristics for dealing with any Predicate)
00200
00300 Each of these heuristics can be assumed to be prefaced by a clause of
00400 the form ``If the current task is to deal with concept X, where X isa
00500 Predicate,...". This will be repeated below, for each rule.
00600
00700 .HH(Predicate,Fillin)
00800
00900 .BH
01000
01100 λλ If the current task was (Fill-in examples of X),
01200
01300 and X is a predicate,
01400
01500 and more than 100 items are known in the domain of X,
01600
01700 and at least 10 cpu seconds were spent trying to randomly instantiate
01800 X,
01900
02000 and the ratio of successes/failures is both >0 and less than .05
02100
02200 .OOO
02300
02400 Then add the following task to the agenda: (Fill-in generalizations
02500 of X), for the following reason:
02600
02700 ``X is rarely satisfied; a slightly less restrictive concept might be
02800 more interesting".
02900
03000 This reason's rating is computed as three times the ratio of
03100 nonexamples/examples found.
03200
03300 .E
03400
03500 .MAH7: BNN;
03600
03700 This rule says to generalize a predicate if it rarely succeeds
03800 (returns T). One use for this was when Equality was found to be
03900 quite rare; the resultant generalizations did indeed turn out to be
04000 more valuable (numbers). A similar use was found for predicates
04100 which tested for identical equality of two angles, of two triangles,
04200 and of two lines. Their generalizations were also valuable
04300 (congruence, similarity, parallel, equal-measure). Most rules in
04400 this appendix are not presented with the same level of detail as the
04500 preceding one, as the reader has no doubt observed.
04600
04700 .BH
04800
04900 λλ To fill in Domain/range entries for predicate P,
05000
05100 P can operate on the domain of any specialization of P,
05200
05300 P can operate on any specialization of the domain of P,
05400
05500 P can operate on some restriction of the domain of any generalization
05600 of P,
05700
05800 P may be able to operate on some enlargement of its current domain,
05900
06000 The range of P will necessarily be the doubleton set {T,F},
06100
06200
06300 P is guaranteed return T if any of its specializations do, and F if
06400 any of its generalizations do.
06500
06600 .E
06700
06800 This contains a compiled version of what we mean when we say that one
06900 predicate is a generalization or specialization of another. Viewed as
07000 relations, as subsets of a Cartesian-product of spaces, this notion
07100 of general/special is just that of superset/subset. The last line of
07200 the rule is meant to indicate that adding new constraints onto P can
07300 only make it return True less frequently, while relaxing P's
07400 definition can only make it return True more often.
07500
07600
07700 .HH(Predicate,Suggest)
07800
07900 .BH
08000
08100 λλ If all the values of Active concept F happen to be Truth-values,
08200 and F is not known to be a predicate,
08300
08400 Then conjecture that F is in fact a predicate.
08500
08600 .E
08700
08800 .MAH8: BNN;
08900
09000 This rule is placed on the Suggest facet because, if placed anywhere
09100 else on this concept, it could only be seen as relevant by AM if AM
09200 already knew that F were a predeicate. On the other hand, the rule
09300 can't be placed, e.g., on Active.Fillin, since just forgetting
09400 (deleting) this ``Predicate" concept should be enough to delete all
09500 references to predicates anywhere in the system.
09600
09700
09800 .HH(Predicate,Interest)
09900
10000 .BH
10100
10200 λλ A predicate P is interesting if its domain is Any-concept (the
10300 space of all known concepts). This is especially true if there is a
10400 significant positive correlation (theoretical or empirical) between
10500 concepts' worths and their P-values.
10600
10700 .E
10800
10900 This very high level heuristic wasn't really used by AM during its
11000 runs.
11100
00100 .ASSEC(Heuristics for dealing with any Operation)
00200
00300 .HH(Operation,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in examples of operation F (with domain A and range B),
00800
00900 when many examples αα of A are already known,
01000
01100 and F maps some of those examples αα into distinguished members (esp:
01200 extrema) b of B,
01300
01400 Then (for each such distinguished member ``b"εB) study F-1-(b) as a
01500 new concept. That is, isolate those members of A whose F-value is
01600 the unusual item bεB.
01700
01800 .E
01900
02000 This rule says to investigate the inverse image of an unusual item b,
02100 under the interesting operation f. When b=2 and
02200 f=number-of-divisors-of, this rule leads to the definition of prime
02300 numbers. When b=Phi$$ the empty set, NIL, α{α} $ and f=Intersection,
02400 the rule led to the discovery of the concept of disjointness of sets.
02500
02600 .BH
02700
02800 λλ To fill in Domain/range entries for operation F,
02900
03000 F can operate on the domain of any specialization of F,
03100
03200 F can operate on the specialization of the domain of any
03300 specialization of F (including F itself),
03400
03500 F can operate on some restriction of the domain of any generalization
03600 of F, at least on its current domain and perhaps even on a bigger
03700 space,
03800
03900
04000 F may be able to operate on some generalization of (some component(s)
04100 of) its current domain,
04200
04300 F can only (and will always) produce values lying in the range of
04400 each generalization of F,
04500
04600 F can -- with the proper arguments -- produce values lying in the
04700 range of any particular specialization of F.
04800
04900 .E
05000
05100 There are only a few changes between this rule and the corresponding
05200 one for Predicates. Recall that Operations can be multi-valued, and
05300 those values are not limited to the set α{T,Fα}.
05400
05500 .BH
05600
05700 λλ To fill in Domain/range entries for operation F, when some exist
05800 already,
05900
06000 Take an entry of the form <D1 D2... Dn → R> and see if DixR is
06100 meaningful for some i (especially: i=n).
06200
06300 If so, then remove Di from the left side of the entry, and replace R
06400 by DixR, and modify the definition of F.
06500
06600 .E
06700
06800 In LISP, ``meaningful" is coded as: either D⊗7i⊗6x⊗1R is equivalent to
06900 an already-known concept, or else it is found in at least two
07000 interesting conjectures. This is probably an instance of what
07100 McDermott calls natural stupidity$$ See [McDermott 76] for natural
07200 stupidity. He criticizes the use of very intelligent-sounding names
07300 for otherwise-simple program modules. But consider ``Homo sapiens",
07400 which means ``wise man". Now ↓_there's_↓ a misleading label...$. This
07500 rule is tagged as being explosive, and is not used very often by AM.
07600
07700 .BH
07800
07900 λλ To fill in a Range entry for operation F,
08000
08100 Run F on various domain examples, especially boundary examples, to
08200 collect examples of the range. Then ripple down the tree of concepts
08300 to determine empirically where F seems to be sending its values.
08400
08500 .E
08600
08700 .MAH9: BNN;
08800
08900 This may shock the reader, as it sounds dumb and explosive, but the
09000 concepts are arranged in a tree (using Genl links), so the search is
09100 really quite fast. Although this rule is rarely used, it always
09200 seems to give surprisingly good results.
09300
09400 .BH
09500
09600 λλ If operation F has just been applied, and has yielded a new concept
09700 C as its result,
09800
09900 Then carefully examine F.Dom/range to try to find out what C.Isa
10000 should be. C.Isa will be all legal entries listed as values of the
10100 range of F.
10200
10300 .E
10400
10500 .GETRR: BNN;
10600
10700 .GETRRP: PAGE;
10800
10900 When F=Compose, say AM has just created C=Empty-o-Insert.$$i.e.,
11000 insert x into a structure S and then see if S is empty. This leads AM
11100 to realize that inserting can never result in an empty structure. $
11200 What is C? It is a concept, of course, but what else? By examining
11300 the Domain/range facet of Compose, AM finds the entry <Active Active
11400 α→ Active>. Aha! So C must be an Active. But AM also finds the entry
11500 <Predicate Active α→ Predicate>. Since ``Empty" is a predicate, the
11600 final composition C must also be a predicate. So C.Isa would be
11700 filled in with ``Predicate". AM thus used the above rule to determine
11800 that Empty-o-Insert was a predicate. Even if this rule were excised,
11900 AM could still determine that fact, painfully, by noticing that all
12000 the values were truth-values.
12100
12200 .BH
12300
12400 λλ If operation F has just been applied to A1,A2,..., and has yielded
12500 a new concept C as its result,
12600
12700 Then add F to C.In-ran-of; add F to the In-dom-of facet of all the
12800 Ai's which are concepts; add <A1... α→ C> to F.Exs.
12900
13000 .E
13100
13200 There is some overlap here with earlier rules, but there is no
13300 theoretical or practical difficulty with such redundancy.
13400
13500 .BH
13600
13700 λλ When filling in examples of operation F, if F takes some existing
13800 concepts A1, A2,... and (may) produce a new concept,
13900
14000 Then only consider, as potential A↓i's, those concepts which already
14100 have some examples. Prefer the A↓i's to be interesting, to have a
14200 high worth rating, to have some interesting conjectures about them,
14300 to have several examples and several non-examples, etc.
14400
14500 .E
14600
14700 .HAVEX: BNN;
14800
14900 The danger here is of, e.g., Composing two operations which turn out
15000 to be vacuous, or of Conjoining an empty concept onto another, or of
15100 proliferating variants of a boring concept, etc.
15200
15300
15400
15500 .HH(Operation,Check)
15600
15700 Below are rules used to check existing entries on various facets of
15800 operations.
15900
16000 .BH
16100
16200 λλ To check the domain/range entries on the operation F,
16300
16400 IF a domain/range entry has the form (D D D... → R),
16500
16600 and all the D's are equal, and R is a generalization of D (or, with
16700 less enthusiasm: if R and D have a significant overlap),
16800
16900 THEN it's worth seeing whether (D D D... → D) is consistent with all
17000 known examples of the operation:
17100
17200 .INDENT 12,16,0
17300
17400 If there are no known examples, add a task to the agenda requesting
17500 they be filled in.
17600
17700 If there are examples, and (D D D... → D) is consistent, add it to
17800 the Domain/range facet of this operation.
17900
18000 If there are some contradicting examples, create a new concept which
18100 is defined as this operation restricted to (D D D... → D).
18200
18300 .E
18400
18500 When AM restricts Bag-union to numbers (bags of T's), the new
18600 operation has a Domain/range entry of the form (Numbers Numbers →
18700 Bag). The above rule has AM investigate whether the range
18800 specification mightn't also be narrowed down to Number. In this case
18900 it is a great help. The rule often fails, of course: the sum of two
19000 primes is rarely a prime, the cross-product of two lists-of-atoms is
19100 not a list-of-atoms, etc. Since this rule is almost instantaneous to
19200 execute, it's cost-effective overall.
19300
19400 .BH
19500
19600 λλ When checking the domain/range entries on the operation F,
19700
19800 IF a domain/range entry has the form (D D D... → R),
19900
20000 and all the D's are equal, and R is a specialization of D,
20100
20200 THEN it's worth inserting (D D D... → D) as a new entry on F.Dom/ran,
20300 even though that is redundant.
20400
20500 .E
20600
20700 This shows that symmetry and aesthetics are sometimes preferable to
20800 absolute optimization. That's why we program in Lisp, instead of
20900 machine language. On the other hand, this rule wasn't really that
21000 useful to AM. Now, by analogy,...?
21100
21200 .BH
21300
21400 λλ When checking the Domain/range entries for operation F,
21500
21600 Ensure that the boundary items in the range can actually be reached
21700 by F. If not, see whether the range is really just some known
21800 specialization of F.
21900
22000 .E
22100
22200 This rule is a typical checking rule. Note that it is active, not
22300 passive: it might alter the Domain/range facet of F, it it finds an
22400 error there.
22500
22600 .BH
22700
22800 λλ When checking examples of the operation F, for each such example,
22900
23000 If the value returned by F is a concept C, add `F' to C.In-range-of.
23100
23200 .ES
23300
23400
23500 .HH(Operation,Suggest)
23600
23700 .BH
23800
23900 λλ Whenever the domain of operation F has changed,
24000
24100 check whether the range has also changed. Often the range will change
24200 analogously to the domain, where the operation itself is the Analogy.
24300
24400 .E
24500
24600 .BH
24700
24800 λλ After working on Operation F,
24900
25000 Give a slight, ephemeral boost to tasks involving Range(F).
25100
25200 .E; ONCE TURN ON ``{}``;
25300
25400 This wll be a moderate size boost for each task which asks to fill in
25500 examples of that range concept, and a very tiny boost for each other
25600 task mentioning such a concept. This is both a supplement to the
25700 more general ``focus of attention" rule, and a nontrivial heuristic
25800 for finding valuable new tasks. It is an extension of rule number
25900 {[3]FROB2}, and a partial converse to rule {[3]FROB1}.
26000
26100
26200
26300 .HH(Operation,Interest)
26400
26500 .BH
26600
26700 λλ An operation F is interesting if there are other operations with
26800 the same domain and range, and if they are (on the average) fairly
26900 interesting.
27000
27100 .ES
27200
27300 .BH
27400
27500 λλ An operation F is interesting if it is the first operation
27600 connecting its domain concept to its range concept, and if those
27700 domain/range components are themselves valuable concepts, and there
27800 is no analogy between them, and there are some interesting
27900 conjectures involving the domain of F.
28000
28100 .E
28200
28300 The above two rules say that F can be valuable becuase it's similar
28400 to other, already-liked operations, or because it is totally
28500 different from any known operation. Although these two criteria are
28600 nonintersecting, their union represents only a small fraction of the
28700 operations that get created: typically, ⊗4neither\0 rule will
28800 trigger.
28900
29000 .BH
29100
29200 λλ An operation F is interesting if its range is very interesting.
29300
29400 .E
29500
29600 .IRAN: BNN; ONCE TURN ON ``{}``;
29700
29800 Range here refers to the concept in which all results of F must lie.
29900 It is the R in the domain/range facet entry <D → R> for concept F.
30000 The corresponding rule for `domains' is applicable to any Active, not
30100 just to Operations, hence is listed under Active.Interest, as rule
30200 number {[3]IIDOM}.
30300
30400
30500 .BH
30600
30700 λλ An operation F is interesting if the values of F satisfy some
30800 unusual property which is not (in general) satisfied by the arguments
30900 to F.
31000
31100 .E
31200
31300 Thus doubling is interesting because it always returns an even
31400 number. This is one case where the interesting property can be
31500 deduced trivially just by looking at the domain and range of the
31600 operation: Numbers→Even-nos.
31700
31800
31900 .BH
32000
32100 λλ An operation is interesting if its values are interesting.
32200
32300 .E
32400
32500 .ONCE TURN ON ``{}``
32600
32700 This can mean that each value is interesting (e.g., Compose is
32800 well-received because it produces many new, valuable concepts as its
32900 values). Or, it can mean that the operations' values, gathered
33000 together into one big set, are interesting as a set. Unlike the
33100 preceding rule, this one has no mention whatsoever of the domain
33200 items, the arguments to the operation. This rule was used to good
33300 advantage frequently by AM. For example, Factorings of numbers are
33400 interesting because (using rule {[3]SRI1}) for all x, Factorings(x)
33500 is interesting in exactly the same way. Namely, Factorings(x),
33600 viewed as a set, always contains precisely one item which has a
33700 certain interesting property (see rule {[3]SRI2}). Namely, all its
33800 members are primes (see rule {[3]SRI1} again). This explains one way
33900 in which AM noticed that all numbers seem to factor uniquely into
34000 primes.
34100
34200 .BH
34300
34400 λλ An operation is interesting if its values are interesting,
34500 ignoring the images of boundary items from the domain.
34600
34700 .E
34800
34900 That is, if the image of the domain -- minus its boundary -- is
35000 interesting.
35100
35200 .BH
35300
35400 λλ An operation is interesting if its values on the boundary items
35500 from the domain are very interesting. Ignore the non-boundary parts
35600 of the domain.
35700
35800 .E
35900
36000 That is, if the image of the boundary of the domain is interesting.
36100
36200 .BH
36300
36400 λλ An operation is interesting if it leaves intact any interesting
36500 properties of its argument(s). This is even better if it eliminates
36600 some undesirable properties, or adds some new, desirable ones.
36700
36800 .E
36900
37000 Thus a new, specialized kind of Insertion operation is interesting
37100 if, even though it stuffs more items into a structure, the nice
37200 properties of the structure remain. The operation ``Merge" is
37300 interesting for this very reason: it inserts items into an
37400 alphabetized list, yet it doesn't destroy that interesting property
37500 of the list.
37600
37700
37800 .BH
37900
38000 λλ An operation is interesting if its domain and range are equal. If
38100 there is more than one domain component, then at least one of them
38200 should equal the range. The more components which are equal to the
38300 range, the better.
38400
38500 .DRCO: BNN;
38600
38700 .E
38800
38900 Thus ``Insertion" qualifies here, since its domain/range entry is
39000 <Anything Structures α→ Structures>. But ``Union" is even better,
39100 since both domain components equal the range, namely Structures.
39200
39300 .BH
39400
39500 λλ An operation is mildly interesting if its range is related somehow
39600 (e.g. specialization of) to one or more components of its range. The
39700 more the better.
39800
39900 .E
40000
40100 A weakened form of the preceding rule.
40200
40300 .BH
40400
40500 λλ If the result of applying operation F is a new concept C,
40600
40700 Then the interestingness of F is weakly tied to that of C.
40800
40900 .E
41000
41100 If the new concept C becomes very valuable, then F will rise slightly
41200 in interest. If C is so bad it gets forgotten, F will not be
41300 regarded quite as highly. When Canonize scores big its first time
41400 used, it rises in interest. This caused AM to form poorly-motivated
41500 canonizations, which led to dismal results, which gradually lowered
41600 the rating of Canonize to where it was originally.
41700
00100 .ASSECP(Heuristics for dealing with any Composition)
00200
00300 .COMPH: SSECNUM;
00400
00500 .COMPHP: PAGE;
00600
00700 .HH(Composition,Fillin)
00800
00900 .BH
01000
01100 λλ To fill in algorithms for operation F, where F is a composition G-o-H,
01200
01300 One algorithm is: apply H and then apply G to the result.
01400
01500 .E
01600
01700 Of course this rule is not much more than the definition of what it means
01800 to compose two operations.
01900
02000 .BH
02100
02200 λλ To fill in Domain/range entries for operation F, where F is a composition G-o-H,
02300
02400 Tentatively assume that the domain is Domain(H), and range is Range(G).
02500 More precisely, the domain will be the result of substituting
02600 Domain(H) for Range(H) wherever Range(H) appears (or: just once) in Domain(G).
02700
02800 .E
02900
03000 .CDRH1: BNN;
03100
03200 Thus for F=Divides-o-Count, where Divides:<Number,Number → {T,F}>, and
03300 Count:<Bag → Number>, the above rule
03400 would say that the domain/range entries for F are gotten by substituting
03500 `Bag' for `Number' once or twice in Domain(Divides). The possible entries for
03600 F.Dom/range are thus:
03700 <Bag,Bag → {T,F}>,
03800 <Number,Bag → {T,F}>,
03900 and <Bag,Number → {T,F}>.
04000
04100 .BH
04200
04300 λλ To fill in Domain/range entries for operation F, where F is a composition G-o-H,
04400 But Range(H) does not occur as a component of Domain(G),
04500
04600 The range of F is still Range(G), but the domain of F is computed as follows:
04700 Ascertain the component X of Domain(G) having the biggest (fractional) overlap
04800 with Range(H). Then substitute Domain(H) for X in Domain(G). The result is
04900 the value to be used for Domain(F).
05000
05100 .E
05200
05300 .CDRH2: BNN;
05400
05500 This rule is a second-order correction to the previous one. If there is
05600 no absolute equality, then a large intersection will suffice. Notice that
05700 F may no longer be defined on all of its domain, even if G and H are.
05800 If identical equality is taken as the maximum possible overlap betwen two
05900 concepts, then this rule can be used to replace the preceding one completely.
06000
06100
06200 .BH
06300
06400 λλ When trying to fill in the Isa entries for a composition F=G-o-H,
06500
06600 Examine G.Isa and H.Isa, and especially their intersection. Some of those
06700 concepts may also claim F as an example. Run their definition facet to see.
06800
06900 .E; ISARG: BNN; ISARGP: PAGE; ONCE TURN ON ``{}``;
07000
07100 To see how this is encoded into LISP, turn to page {[3]ISARGP2}.
07200
07300 .BH
07400
07500 λλ When trying to fill in the Genl or Spec entries for a composition F=G-o-H,
07600
07700 Examine the corresponding facet on G and on H.
07800
07900 .E
08000
08100 This rule is similar to the preceding one, but wasn't as useful or as reliable.
08200
08300 .BH
08400
08500 λλ A satisfactory initial guess at the Worth value of composition F=G-o-H is
08600 the root-sum-of-squares of G.Worth and H.Worth.
08700
08800 .ES
08900
09000 .BH
09100
09200 λλ To fill in examples of F, where F=G-o-H, and both G and H are time-consuming,
09300 but where many examples of both G and H exist,
09400
09500 Seek an example x→y of H, and an example y→z of G, and then return x→z as a
09600 probable example of F.
09700
09800 .E
09900
10000 Above, `seek' is done in a tight, efficent manner. The examples are H are hashed
10100 into an array, based on the values y of each one. Then the arguments of the examples
10200 of G are hashed to see if they occur in this array. Those that do will generate
10300 an example of the new composition.
10400
10500 .BH
10600
10700 λλ To fill in examples of F, where F=G-o-H, and G is timeconsuming,
10800 but many examples of G exist,
10900 and it is not known whether H is time-consuming or not,
11000
11100
11200 Spend a moment trying to access or trivially fill in examples of H.
11300
11400 If this succeeds, apply the preceding rule.
11500
11600 If this fails, then formally propose that AM fill in examples of H,
11700 with priority equal to that of the current task, for these two reasons:
11800 (i) if examples of H existed, then AM could have used the heuristic preceding
11900 this one, to fill in examples of F, and (ii) it is dangerous to spend a long time
12000 dealing with G-o-H before any examples at all of H are known.
12100
12200
12300 .E
12400
12500 This rule is of course tightly coupled to the preceding one.
12600 The same rule exists for the case where just H is time-consuming, instead of G.
12700
12800 .BH
12900
13000 λλ When trying to fill in Conjecs about a composition F=G-o-H,
13100
13200 Consider that F may be the same as G (or the same as H).
13300
13400 .E
13500
13600 It was somewhat depressing that this `stupid' heuristic turned out to be
13700 valuable, perhaps even necessary for AM's top performance.
13800
13900
14000
14100
14200 .HH(Composition,Check)
14300
14400 .BH
14500
14600 λλ Check that F-o-G is really not the same as F, or the same as G.
14700 Spend some time checking whether F-o-G is equivalent to any already-known active
14800 concept.
14900
15000 .E
15100
15200 This happens often enough to make it worth stating explicitly. Often, for example,
15300 F will not even bother looking at the result of G! For example,
15400
15500 .ONCE INDENT 0; PREFACE 0; RETAIN;
15600
15700 Proj2-o-Square(x,y) = Proj2(Square(x),y) = y = Proj2(x,y).
15800
15900 .BH
16000
16100 λλ When checking the Algorithms entries for a composition F=G-o-H,
16200
16300 If range(H) is not wholly contained in the domain of G,
16400
16500 then the algorithm must contain a ``legality" check, ensuring that H(x) is a valid
16600 member of the domain of G.
16700
16800 .E
16900
17000
17100 .HH(Composition,Suggest)
17200
17300 .BH
17400
17500 λλ Given an interesting operation F:A↑n→A,
17600
17700 consider composing F with itself.
17800
17900 .E
18000
18100 .EVAD1: BNN;
18200
18300 This may result in more than one new operation. From F=division,
18400 for example, we get the two operations (x/y)/z and x/(y/z).
18500 AM quickly realizes that such variants are really equivalent,
18600 and (if prodded) eventually realizes that F(F(x,y),z)=F(x,F(y,z)) is a common
18700 situation (which we call associativity of F).
18800
18900 .BH
19000
19100 λλ If the newly-formed domain of the composition F=G-o-H contains more
19200 than one occurrence of the concept D, and this isn't true of G or H,
19300
19400 Then consider creating a new operation, a specialization of F,
19500 by Coalescing the domain/range of F, by eliminating one of the D components.
19600
19700 .E
19800
19900 .COAC: BNN;
20000
20100 Thus when Insert-o-Delete is formed, the old Domain/range entries were
20200 both of the form <Anything Structure → Structure>. The newly-created entry
20300 for Insert-o-Delete was <Anything Anything Structure → Structure>; i.e.,
20400 take x, delete it from S, then insert y into S. The above rule had AM
20500 turn this into a new operation, with domain/range <Anything Structure → Structure>,
20600 which deleted x from S and the inserted the very same x back into S.
20700
20800
20900 .HH(Composition,Interest)
21000
21100 .COMI: PAGE;
21200
21300 .BH
21400
21500 λλ A composition F=G-o-H is interesting if G and H are very interesting.
21600
21700 .ES
21800
21900 .BH
22000
22100 λλ A composition F=G-o-H is interesting if F has an interesting property
22200 not possessed by either G or H.
22300
22400 .ES
22500
22600 .BH
22700
22800 λλ A composition F=G-o-H is interesting if F has most of the interesting properties
22900 which are possessed by either G or H.
23000 This is slightly reduced if both G and H possess the property.
23100
23200 .ES
23300
23400 .BH
23500
23600 λλ A composition F=G-o-H is interesting if F lacks any undesirable properties
23700 true of G or H.
23800 This is greatly increased if both G and H possess the bad property, unless
23900 G and H are very closely related to each other (e.g., H=G,or H=G-1-).
24000
24100 .E
24200
24300 The numeric impact of each of these rules was guessed at initially, and
24400 has never needed tuning. Here is an area where experimentation might prove
24500 interesting.
24600
24700 .BH
24800
24900 λλ A composition F=G-o-H is interesting if F maps interesting subsets of domain(H)
25000 into interesting subsets of range(G).
25100
25200 F is to be judged even
25300 more interesting
25400 if the image was not thought to be interesting until
25500 after it was explicitly isolated and studied because of part 1 of this very rule.
25600
25700 .E
25800
25900 Here, an ``interesting" subset of domain(H) is one so judged by Interests(domain(H)).
26000 A completely different set of criteria will be used to judge the interestingness of
26100 the resultant image under F. Namely, for that purpose, AM will ask
26200 for range(G).Interest, and ripple outwards to look for related interest features.
26300
26400 .BH
26500
26600 λλ A composition F=G-o-H is interesting if F-1- maps interesting subsets of range(G)
26700 into interesting subsets of domain(F).
26800
26900 This is even better if the preimage
27000 wasn't hitherto realized as interesting.
27100
27200 .E
27300
27400 This is the converse of the preceding rule. Again, ``interesting" is judged by two
27500 different sets of criteria.
27600
27700 .BH
27800
27900 λλ A composition F=G-o-H is interesting if F maps interesting elements of domain(H)
28000 into interesting subsets of range(G).
28100
28200 .ES
28300
28400 .BH
28500
28600 λλ A composition F=G-o-H is interesting if F-1- maps interesting elements of range(G)
28700 into interesting subsets of domain(F).
28800
28900 This is even better if the subset is only now seen to be interesting.
29000
29100 .E
29200
29300 This is the analogue of an earlier rule, but for individual items rather
29400 than for whole subsets of the domain and range of F.
29500
29600 .BH
29700
29800 λλ A composition F=G-o-H is interesting if range(H) is equal to, not just intersects,
29900 one component of domain(G).
30000
30100 .ES
30200
30300 .BH
30400
30500 λλ A composition F=G-o-H is mildly interesting if range(H) is a specialization of
30600 one component of domain(G).
30700
30800 .E
30900
31000 This is a weakened version of the preceding feature. Such a composition is interesting
31100 because it is guaranteed to always be applicable. If Range(H) merely intersects
31200 a domain component of G, then there must be an extra check, after computing
31300 H(x), to ensure it lies within the legal domain of G, before trying to run G on that
31400 new entity H(x).
31500
31600 .BH
31700
31800 λλ A composition F=G-o-H is more interesting if range(G) is equal to a domain component
31900 of H.
32000
32100 .E ONCE TURN ON ``{}``
32200
32300 This is over and above the slight boost given to the composition because
32400 it is an ⊗4operation\0
32500 whose domain
32600 and range coincide (see rule {[3]DRCO}).
32700
32800
00100 .ASSEC(Heuristics for dealing with any Insertions)
00200
00300 .HH(Insertion,Check)
00400
00500 .BH
00600
00700 λλ When checking an example of any kind of insertion of x into S,
00800
00900 Ensure that x is a member of S.
01000
01100 .E
01200
01300 The only types of insertions known to AM are ⊗4unconditional\0 insertions,
01400 so this rule is valid. It is useful for ensuring that a particular new operation
01500 really is an insertion-operation after all!
01600
00100 .ASSEC(Heuristics for dealing with the operation Coalesce)
00200
00300 .HH(Coalesce,Fillin)
00400
00500 .BH
00600
00700 λλ When coalescing F(a,b,c,...), whose domain/range is <A B C... →
00800 R>,
00900
01000 A good choice of two domain components to coalesce is a pair of
01100 identically equal ones. Barring that, choose a pair related by
01200 specialization (eliminate the more general one). Barring that, choose
01300 a pair with a common specialization S, and replace both by S.
01400
01500 .E
01600
01700 Thus to coalesce the operation ``Insert-o-Delete" [which takes two
01800 items and a structure, deletes the first argument from the structure
01900 and then inserts the second argument], AM examines its Domain/range
02000 entry: <Anything Anything Structure → Structure>. Although it would
02100 be legal to collapse the second and third arguments, the above rule
02200 says it makes more sense in general to collapse the first and second.
02300 In fact, in that case, AM gets an operation which tells it something
02400 about multiple elements structures.
02500
02600 .BH
02700
02800 λλ When filling in Algorithms for a coalesced version G of active
02900 concept F,
03000
03100 One natural algorithm is simply to call on F.Algs, with two arguments
03200 the same.
03300
03400 .E
03500
03600 Of course the two identical arguments are those which have been
03700 decided to be merged. This will be decided before the definition and
03800 algorithm facets are filled in. Thus a natural algorithm for Square
03900 is to call on TIMES.Alg(x,x). The following rule is similar:
04000
04100 .BH
04200
04300 λλ When filling in Definitions for a coalesced version G of active
04400 concept F,
04500
04600 One natural Definition is simply to call on F.Defn, with two
04700 arguments the same.
04800
04900 .ES
05000
05100 .BH
05200
05300 λλ When filling in the Worth of a new coalesced version of F,
05400
05500 A suitable value is 0.9x(Worth of F) + 0.1x(Worth of Coalesce).
05600
05700 .E
05800
05900 This is a compromise between (i) the knowledge that the new operation
06000 will probably be less interesting than F, and (ii) the knowledge that
06100 it may lead to even more valuable new concepts (e.g., ⊗4its\0 inverse
06200 may be more interesting than F's). The formula also incorporates a
06300 small factor which is based on the overall value of coalescings which
06400 AM has done so far in the run.
06500
06600
06700
06800 .HH(Coalesce,Check)
06900
07000 .BH
07100
07200 λλ If G and H are each two coalescings away from F, for any F,
07300
07400 Then check that G and H aren't really the same, by writing their
07500 definitions out in terms of F.Defn.
07600
07700 .E; ONCE TURN ON ``{}``
07800
07900 Thus if R(a,b,c) is really F(a,b,a,c), and S(a,b,c) is really
08000 F(a,b,c,c), and R and S get coalesced again, into G(a,b) whch is
08100 R(a,b,a) and into H(a,b) which is S(a,b,a), then both G and H are
08200 really F(a,b,a,a). The order of coalescing is unimportant. This is
08300 a boost to the more general impetus for checking this sort of thing,
08400 rule {[3]SOFSC}. This rule is faster, containing a special-purpose
08500 program for untangling argument-calls rapidly. If the concept of
08600 Coalesce is excised from the system, one can easily imagine it being
08700 re-derived by a more general `coincidence' strategy, but how will
08800 these specific, high-powered, tightly-coded heuristics ever get
08900 discovered and tacked onto the Coalesce concept? This is an instance
09000 of the main meta-level research problem proposed earlier in the
09100 book (Chapter {[2]EVALU}).
09200
09300
09400
09500 .HH(Coalesce,Suggest)
09600
09700 .BH
09800
09900 λλ If a newly-interesting active concept F(x,y) takes a pair of N's
10000 as arguments,
10100
10200 Then create a new concept, a specialization of F, called F-Itself,
10300 taking just one N as argument, defined as F(x,x), with initial worth
10400 Worth(F).
10500
10600 If AM has never coalesced F before, this gets a slight bonus value.
10700
10800 If AM has coalesced F before, say into S, then modify this
10900 suggestion's value according to the current worth of S.
11000
11100 The lower the system's interest-threshhold is, the more attactive
11200 this suggestion becomes.
11300
11400 .E
11500
11600 AM used this rule to coalesce many active concepts. Times(x,x) is
11700 what we know as squaring; Equality(x,x) turned out to be the constant
11800 predicate True; Intersect(x,x) turned out to be the identity
11900 operator; Compose(f,f) was an interesting ``iteration" operator$$
12000 e.g., Compose(Compose,Compose) is an operator which takes 3
12100 operations f,g,h and forms ``f o g o h"; i.e., their joint composition.
12200 $; etc. This rule is really a bundle of little meta-rules
12300 modifying one suggestion: the suggestion that AM coalesce F. The
12400 very last part of the above rule indicates that if the system is
12500 desparate, this is the least distasteful way to ``take a chance" on a
12600 high-payoff high-risk course of action. It is more sane than, e.g.,
12700 randomly composing two operations until a nice new one is created.
12800
12900 .BH
13000
13100 λλ If concept F takes only one argument,
13200
13300 Then it is not worthwhile to try to coalesce it.
13400
13500 .E
13600
13700 This rule was of little help cpu-timewise, since even if AM tried to
13800 coalesce such an active concept,it would fail almost instantaneously.
13900 The rule did help make AM appear smarter, however.
14000
00100 .ASSEC(Heuristics for dealing with the operation Canonize)
00200
00300 .HH(Canonize,Fillin)
00400
00500 .BH
00600
00700 λλ If the task is to Canonize predicates P1 and P2 (over AxA)$$ That
00800 is, find a function F such that P1(x,y) iff P2(F(x),F(y)). $, and the
00900 difference between a definition of P1 and definition of P2 is just
01000 that P2 performs some extra check that P1 doesn't,
01100
01200 Then F should convert any aεA into a member of A which automatically
01300 satisfies that extra constraint.
01400
01500 .E; ONCE TURN ON ``{}``
01600
01700 Thus when P1=Same-length, P2=Equality, A=Lists, the extra constraint
01800 that P2 satisfies is just that it recurs in the CAR direction: the
01900 CARs of the two arguments must also satisfy P2. P1 doesn't have such
02000 a requirement. The above rule then has AM seek out a way to guarantee
02100 that the CARs will always satisfy Equality. A special hand-crafted
02200 piece of knowledge tells AM that since ``T=T" is an example of
02300 Equality, one solution is for all the CARs to be the atom T. Then the
02400 operation F must contain a procedure for converting each ember of a
02500 structure to the atom ``T". Thus (A C α{Z A Bα} Q Q) would be
02600 converted to (T T T T T). This rule is a specialized, ``compiled"
02700 version of the idea expressed in rule number {[3]LOOKDIF}.
02800
02900 .BH
03000
03100 λλ If the task is to Canonize P1 and P2 over AxA, trying to
03200 synthesize F, where A=Structure,
03300
03400
03500 Then perhaps there is a distinguished type of structure B which the
03600 argument to F should always be converted into. In that case,
03700 consider P1 and P2 as two predicates over BxB.
03800
03900 .E
04000
04100 This special-purpose rule is used to guide a series of experiments,
04200 to determine whether P1 is affected by adding multiple copies of
04300 existing elements into its arguments, and whether its value is
04400 affected by rearranging some of its arguments' elements. In the case
04500 of P1=Same-size, the answers are: multiple elements do make a
04600 difference, but rearrangement doesn't. So the canonical type of
04700 structure for F=Size must be one which is Mult-eles-allowed and also
04800 one which is Unordered. Namely, a Bag. Thus F is modified so that it
04900 first converts its argument to a Bag. Then Equality and Same-size
05000 are viewed as taking a pair of Bags, and Size is viewed as taking one
05100 Bag and giving back a canonical bag.
05200
05300 .BH
05400
05500 λλ After F is created from P1 and P2, as Canonize(P1,P2),
05600
05700 an acceptable value for the worth of F is the maximum of the worths
05800 of P1 and P2.
05900
06000 .E
06100
06200 In the actual Lisp code, an extra small term is added which takes
06300 into account the overall value of all the Canonizations which AM has
06400 recently produced.
06500
06600 .BH
06700
06800 λλ IF the current task has just created a canonical specialization B
06900 of concept A, with respect to predicates P1 and P2, [i.e., two
07000 members of B satisfy P1 iff they satisfy P2],
07100
07200 THEN add the following entry to the Analogies facet of B:
07300
07400 .TABS 24,29,34 TURN ON ``\``
07500
07600 \<A\P1\Operations-on-and-into(A)>
07700
07800 \<B\P2\Those operations restricted to B's>
07900
08000 .E
08100
08200 .FOA3: BNN;
08300
08400 This rather incoherent rule says that it's worth taking the trouble
08500 to study the behavior of each operation when it is restricted to
08600 working on standard or ``canonical" items. Moreover, some of the old
08700 relationships may carry over -- or at least have analogues -- in this
08800 restricted world. When numbers are discovered as canonical bags, all
08900 the bag operations are restricted to work on only canonical bags, and
09000 they magically turn into what we know and love as numeric operations.
09100 Many of the old bag-theoretic relationships have numeric analogues.
09200 Thus we knew that the bag-difference of x and x was the empty bag;
09300 this is still true for x a canonical bag, but we would word it as ``x
09400 minus x is zero". This is because the restriction of Bag-difference
09500 to canonical bags (bags of T's) is precisely the operation we call
09600 subtraction.
09700
09800 .BH
09900
10000 λλ When Canonize works on P1, P2 (two predicates), and produces an
10100 operation, F,
10200
10300 Both predicates must share a common Domain, of the form AxA for some
10400 concept A, and the new operation F can have <A α→ A> as one of its
10500 Domain/range entries.
10600
10700 If a canonical specialization (say `B') of A is defined, then the
10800 domain/range of F can actually be tightened to <A α→ B>, and it is
10900 also worth explicitly storing the redundant entry <B α→ B>.
11000
11100 .ES
11200
11300 .BH
11400
11500 λλ In the same situation as the last rule,
11600
11700 One conjecture is that P1 and P2 are equal, when restricted to
11800 working on pairs of B's [i.e., pairs of Canonical A's, A's which are
11900 in F(A), range items for F, items x which are the image F(a) of some
12000 aεA].
12100
12200 .E
12300
12400 After canonizing Equal and Same-size into the new operation Length,
12500 AM conjectures that two canonical bags are equal iff they have the
12600 same size.
12700
12800
12900
13000 .HH(Canonize,Suggest)
13100
13200 .BH
13300
13400 λλ When Canonize works on P1, P2, both predicates over AxA, and
13500 produces an operation F:A→A,
13600
13700 It is worth defining and studying the image F(A); i.e., the totality
13800 of A's which are canonical, already in standard form. When this new
13900 concept Canonical-A is defined, suggest the task ``Fillin Dom/range
14000 entries for Canonical-A".
14100
14200 .E
14300
14400 .MAH10: BNN;
14500
14600 Thus AM studied Canonical-Bags, which turned out to be isomorphic to
14700 the natural numbers. What we've called `Canonical-A' in this rule,
14800 we've referred to simply as `B' in earlier Canonizing rules.
14900
15000 .BH
15100
15200 λλ If P1 is a very interesting predicate over AxA, for some
15300 interesting concept A,
15400
15500 Then look over P1.Spec for some other predicate P2 which is also over
15600 AxA, and which has some interesting properties P1 lacks. For each
15700 such predicate P2, consider applying Canonize(P1,P2).
15800
15900 .ES
16000
16100 .DOCAN: BNN; DOCANP: PAGE;
16200
16300 .BH
16400
16500 λλ After producing F as Canonize(P1,P2) [both predicates over AxA],
16600 and after defining Canonical-A,
16700
16800 It is worth restricting operations in In-dom-of(A) to Canonical-A.
16900 Some new properties may emerge.
17000
17100 .E
17200
17300 Thus after defining Canonical-Bags, AM looked at Bags.In-dom-of. In
17400 that list was the operation ``Bag-union". So AM considered the
17500 restriction of Bag-union to Canonical-bags. Instead of Bag-union
17600 mapping two bags into a new bag, this new operation took two
17700 canonical-bags and mapped them into a new bag. AM later noticed that
17800 this new bag was itself always canonical. Thus was born the operation
17900 we call ``Addition".
18000
18100 .BH
18200
18300 λλ After Canonical-A is produced,
18400
18500 It is marginally worth trying to restrict operations in
18600 In-range-of(A) to map into Canonical-A.
18700
18800 .E
18900
19000 This gives an added boost to picking Union to restrict, since it is
19100 in both Bags.In-dom-of and Bags.In-ran-of. This rule is much harder
19200 to implement, since it demands that the range be restricted. There
19300 are just a few special-purpose tricks AM knows to do this.
19400 Restricting the domain is, by comparison, much cleaner. AM simply
19500 creates a new concept with the same definition, but with a more
19600 restricted domain/range facet. For restricting the range, AM must
19700 insert into the definition a check to ensure that the final result is
19800 inside Canonical-A, not just in A. This leads to a very inefficent
19900 definition.
20000
20100 .BH
20200
20300 λλ After Canonical-A is produced,
20400
20500 It is worthwhile to consider filling in examples (especially
20600 boundary) of that new concept.
20700
20800 .E; ONCE TURN ON ``{}``;
20900
21000 This is above and beyond the slight push which rule {[3]NEWCEX} gives
21100 that task.
21200
21300 .MAH11: BNN;
21400
00100 .ASSEC(Heuristics for dealing with the operation Substitute)
00200
00300 Note that substitution operations are produced via the initial
00400 concepts called Parallel-replace and Parallel-replace2. The following
00500 rules are tacked on there.
00600
00700 .HH(Parallel-replace,Suggest)
00800
00900 .BH
01000
01100 λλ If two different variables are used to represent the same
01200 entity,$$ When we say that x and y represent the same entity, what we
01300 really mean is that they have the same domain of identity (e.g.,
01400 ∀xεBags) and they are equally free (there is a precise logical
01500 definition of all this, but there is little point to presenting it
01600 here.) $ then substitute one for the other.
01700
01800 This is very important if the two occurrences are within the same
01900 entry on some facet of a single concept, and less so otherwise.
02000
02100 The dominant variable should be the one typed out previously to the
02200 user; barring that, the older usage; barring that, the one closest to
02300 the letter ``a" in the alphabet.
02400
02500 .E
02600
02700 This heuristic was used less often -- and proved less impressive --
02800 than was originally anticipated by the author. Since most concepts
02900 were begotten from older ones, they always assumed the same variable
03000 namings, hence there were very few mismatches. A special test was
03100 needed to explicitly check for ``x=y" occurring as a conjunct
03200 somewhere, in which case we removed it and y substituted for x
03300 throughout the conjunction.
03400
03500
03600 .BH
03700
03800 λλ If two expressions (especially: two conjectures) are structurally
03900 similar, and appear to differ by a certain substitution,
04000
04100 Then if the substitution is permissable we have just arrived at the
04200 same expression in various ways, and tag it as such,
04300
04400 But if the substitution is not seen to be tautologous, then a new
04500 analogy is born. Associate the constituent parts of both expressions.
04600 This is made interesting if there are several concepts involved which
04700 are assigned new analogues.
04800
04900 .E
05000
05100 The similar statements of the associativity of Add and Times led to
05200 this rule's identifying them as analogous. If AM had been more
05300 sophisticated, it might have eventually formulated some abstract
05400 algebra concepts like ``semigroup" from such analogies.
05500
00100 .ASSEC(Heuristics for dealing with the operation Restrict)
00200
00300 .HH(Restrict,Fillin)
00400
00500 .BH
00600
00700 λλ When filling in definitions (algorithms) for a restriction R of
00800 the active concept F,
00900
01000 One entry can simply be a call on F.Defn (F.Algs).
01100
01200 .E
01300
01400 Thus one definition of Addition will always be as a call on the old,
01500 general operation `Bag-union.' Of course one major reason for
01600 restricting the domain/range of an activity is that it can be
01700 performed using a faster algorithm! So the above rule was used
01800 frequently if not dramatically.
01900
02000 .BH
02100
02200 λλ When creating a restriction R of the active concept F,
02300
02400 Note that R.Genl should contain F, and that F.Spec should contain R.
02500
02600 .ES
02700
02800 .BH
02900
03000 λλ When creating in a restriction R of the active concept F, by
03100 restricting the domain or range to some specialization S of its
03200 previous value C,
03300
03400 A viable initial guess for R.Worth is F.Worth, augmented by the
03500 difference in worth between S and C. Hopefully, S.Worth is bigger
03600 than C.Worth!
03700
03800 .ES
03900
04000
04100
00100 .ASSEC(Heuristics for dealing with the operation Invert)
00200
00300 .HH(Invert,Fillin)
00400
00500 .BH
00600
00700 λλ When filling in definitions for an Inverse F-1- of the active
00800 concept F,
00900
01000 One ``Sufficent Defn" entry can simply be a blind search through the
01100 examples of F.
01200
01300 .E
01400
01500 If we already knew that 4→16 is an example of Square, then AM can use
01600 the above rule to quickly notice that Square-Inverse.Defn(16,4) is
01700 true. This is almost the ``essence" of inverting an operation, of
01800 course.
01900
02000
02100
02200 .HH(Invert,Suggest)
02300
02400 .BH
02500
02600 λλ After creating an inverted form F-1- of some operation F,
02700
02800 If the only definition and algorithm entries are the ``obvious"
02900 inefficient ones,
03000
03100 Then consider the task: ``Fill in algorithms for F-1-``, because the
03200 old blind search is just too awful to tolerate.
03300
03400 .ES
03500
00100 .ASSEC(Heuristics for dealing with Logical combinations)
00200
00300 Eventually, there may be separate concepts for each kind of logical
00400 connective. For the moment, all Boolean operators are lumped together
00500 here. Their definition is too trivial for a `Fillin' heuristic to be
00600 useful, and even `Check' heuristics are almost pointless.
00700
00800
00900 .HH(Logical-combine,Check)
01000
01100 .BH
01200
01300 λλ The user may sometimes indicate `Conjunction' when he really means
01400 `Repeating'.
01500
01600 .ES
01700
01800 .HH(Logical-combine,Suggest)
01900
02000 .BH
02100
02200 λλ If there is something interesting to say about entities satisfying
02300 the disjunction (conjunction) of two concepts' definitions,
02400
02500 Then consider creating a new concept defined as that logical
02600 combination of the two concepts' definitions.
02700
02800 .ES
02900
03000 .MAH12: BNN;
03100
03200 .BH
03300
03400 λλ Given an implication,
03500
03600 Try to weaken the left side as much as possible without destroying
03700 the validity of the whole implication. Similarly, try to strengthen
03800 the right side of the implication.
03900
04000 .ES
04100
04200 .HH(Logical-combine,Interest)
04300
04400 .BH
04500
04600 λλ A disjunction (conjunction) is interesting if there is a
04700 conjecture which is very interesting yet which cannot be made about
04800 any one disjunct (conjunct).
04900
05000 .E
05100
05200 In other words, their logical combination implies more than any
05300 consituent.
05400
05500 .BH
05600
05700 λλ An implication is interesting if the right side is more
05800 interesting than the left side.
05900
06000 .ES
06100
06200
06300
06400 .BH
06500
06600 λλ An implication is interesting if the right side is interesting yet
06700 unexpected based only on assuming the left side.
06800
06900 .ES
07000
07100
00100 .ASSEC(Heuristics for dealing with Structures)
00200
00300 .HH(Structure,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in examples of a kind of structure S,
00800
00900 Start with an empty S, pluck any other member of Examples(Structure),
01000 and transfer members one at a time from the random structure into the embryonic S.
01100 Finally, check that the resultant S really satisfies S.Defn.
01200
01300 .E
01400
01500 This is useful, e.g., to convert examples of lists into examples of sets.
01600
01700 .BH
01800
01900 λλ To fill in specializations of a kind of structure,
02000
02100 add a new constraint that each member must satisfy,
02200 or a constraint on all pairs of members,
02300 or a constraint on all pairs of distinct members,
02400 or a constraint which the structure as a whole must satisfy.
02500 Such a constraint is often merely a stipulation of being an example of an X,
02600 for some interesting concept X.
02700
02800 .E
02900
03000 Thus AM might specialize Bags into Bags-of-primes,
03100 or into Bags-of-distinct-primes, or into Bags-containing-a-prime.
03200
03300
03400
03500 .HH(Structure,Interest)
03600
03700 .BH
03800
03900 λλ Structure S is mildly interesting if all members of S satisfy the interesting
04000 predicate P, or (equivalently) if they are all accidentally examples of
04100 the interesting concept C, or (similarly) if all pairs of members of S
04200 satisfy the interesting binary predicate P, etc.
04300
04400 Also: a KIND of structure is interesting if it appears that each instance of
04500 such a structure satisfies the above condition (for a fixed P or C).
04600
04700 .E
04800
04900 .SRI1: BNN;
05000
05100 Thus a singleton is interesting because all pairs of members satisfy Equal.
05200 The concept ``Singletons" is interesting because each singleton is mildly
05300 interesting in just that same way.
05400 Similarly, AM defines the concept of a bag containing only primes,
05500 because the above rule says it might be interesting.
05600
05700 .BH
05800
05900 λλ A structure is mildly interesting if one member is very interesting.
06000 Even better: exactly one member.
06100
06200 Also: a KIND of structure is interesting if each instance satisfies the
06300 above condition in the same way.
06400
06500 .E
06600
06700 .SRI2: BNN;
06800
06900 Thus the values of ADD-1- are interesting because they always contain
07000 precisely one bag which is a Singleton.
07100
00100 .ASSEC(Heuristics for dealing with Ordered-structures)
00200
00300 .HH(Ordered-struc,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in some new examples of the ordered structure S, when some
00800 already exist,
00900
01000 Pick an existing example and randomly permute its members.
01100
01200 .ES
01300
01400 .BH
01500
01600 λλ To fill in specializations of a kind of ordered structure,
01700
01800 add a new constraint that each pair of adjacent members must satisfy,
01900 or a constraint on all ordered pairs of members in the order they
02000 appear in the structure. Such a constraint is often merely a
02100 stipulation of being an example of an X, for some interesting concept
02200 X.
02300
02400 .E
02500
02600 Thus Lists-of-numbers might be specialized into
02700 Sorted-lists-of-numbers, assuming AM has discovered ``α≤`` and assuming
02800 it is chosen as the `constraint' relationship between adjacent
02900 members of the list.
03000
03100
03200 .HH(Ordered-struc,Check)
03300
03400 .BH
03500
03600 λλ If the structure is to be accessed sequentially until some
03700 condition is met, and if the precise ordering is superfluous,
03800
03900 Then keep the structure ordered by frequency of use, the most useful
04000 element first.
04100
04200 .E
04300
04400 .EVAD2: BNN;
04500
04600 This is a simple data-structure management trick. If you have several
04700 rules to use in a certain situation, and rule R is one which usually
04800 succeeds, then put R first in the list of rules to try. Similarly, in
04900 a pattern-matcher, try first the test most likely to detect
05000 non-matching arguments.
05100
05200 .BH
05300
05400 λλ If structure S is always to be maintained in alphanumeric order,
05500
05600 Then AM can$$ due to the current LISP implementation of
05700 data-structures $ actually maintain it as an unordered structure, if
05800 desired.
05900
06000 .E
06100
06200 Luckily this heavily implementation-dependent rule was never needed
06300 by AM.
06400
06500
06600
06700 .HH(Ordered-struc,Interest)
06800
06900 .BH
07000
07100 λλ An ordered structure S is interesting if each adjacent pair of
07200 members of S satisfies predicate P (for some rare, interesting P).
07300
07400 .E
07500
07600 When AM discovers the relation ``α≤``, it immediately thinks that any
07700 ⊗4sorted\0 list of numbers is more interesting, due to the above
07800 rule.
07900
00100 .ASSEC(Heuristics for dealing with Unordered-structures)
00200
00300 .HH(Unord-struc,Check)
00400
00500 .BH
00600
00700 λλ To check an example of an unordered structure,
00800
00900 Ensure that it is in alphanumerically-sorted order. If not, then SORT
01000 it.
01100
01200 .E
01300
01400 All unordered objects are maintained in lexicographic order, so that
01500 two of them can be tested for equality using the LISP function EQUAL.
01600 Because of this convention, any two structures can therefore be
01700 tested for equality using this fast list-structure comparator.
01800
00100 .ASSEC(Heuristics for dealing with Multiple-eles-structures)
00200
00300 .HH(Mult-ele-struc,Fillin)
00400
00500 .BH
00600
00700 λλ To fill in some new examples of the structure S, where S is a
00800 structure admitting multiple occurrences of the same element, when
00900 some examples already exist,
01000
01100 Pick an existing example and randomly change the multiplicity with
01200 which various members occur within the structure.
01300
01400 .ES
01500
00100 .ASSEC(Heuristics for dealing with Sets)
00200
00300 .HH(Sets,Suggest)
00400
00500 .BH
00600
00700 λλ If P is a very interesting predicate over X,
00800
00900 Then study these two sets: the members of X for which P holds, and
01000 the ones for which P fails.
01100
01200 .E
01300
01400 .MAH13: BNN;
01500
01600 While we humans know that this partitions X into two pieces, AM is never
01700 explicitly told this. It would occasionally be surprised to discover
01800 that the union of two such complements ``accidentally" coincided with
01900 X. Incidentally, this rule is really the key linkage between
02000 predicates and sets; it is close to the entry on Set.View which tells
02100 how to view any predicate as a set.
02200
02300
02400
02500 .HH(Sets,Interest)
02600
02700 .BH
02800
02900 λλ A set S is interesting if, for some interesting predicate P, whose
03000 domain is X,
03100
03200 S accidentally appears to be related strongly to {xεX | P(x)}, i.e.,
03300 to those members of X satisfying P.
03400
03500 .E
03600
03700 To the surprise of the author, this rule never found application in
03800 any of AM's runs.
03900
00100 .TRULES: BNN;
00200